直接上代碼夕晓，詳細(xì)請見注釋或者下方留言。

package cut.point;

import java.util.Scanner;
import java.util.Stack;

/**
 * "轟炸重要城市"問題：
 * 假設(shè)當(dāng)前我們擁有一個 地區(qū)的城市地圖，但是只有一個原子彈，為了讓這顆原子彈發(fā)揮最大的效果檬嘀，要阻斷這個地區(qū)各個城市中最關(guān)鍵的一個交通要塞倒彰，那么這個原子彈該投放在哪里疟游？
 * 其實(shí)真有原子彈就不會考慮這么多了（~……~）呼畸，扯回正題。這種問題模型化之后颁虐，就是讓我們從一個無向連通圖中選擇一個“割點(diǎn)”蛮原，去掉這個點(diǎn)之后，不再是連通圖另绩。
 * 關(guān)鍵詞：DFS儒陨、割點(diǎn)、無向連通圖笋籽、重要城市
 * 特殊說明：有些方法的參數(shù)比較多蹦漠，主要是這次不想用一些全局靜態(tài)變量來處理，所以就全部通過傳參解決车海！
 * @author XZP
 *一組測試數(shù)據(jù)：
6 7 
1 4 
1 3 
4 2
3 2
2 5 
2 6
5 6
 */
public class BombingImportantCity {

    public static void main(String[] args) {
        int INF = 99999; // 人為設(shè)定的最大值
        Scanner sc = new Scanner(System.in);
        int i; // 游標(biāo)
        int v1, v2; //暫時存儲邊兩個頂點(diǎn)的編號
        int n = sc.nextInt(); // 頂點(diǎn)數(shù)
        int m = sc.nextInt(); // 邊的條數(shù)
//      Edge[] edges = new Edge[m + 1]; // 存儲邊的數(shù)組笛园，下標(biāo)從1開始
        int[][] edges = new int[n + 1][n +1]; // 存放邊的鄰接矩陣
        int[] num = new int[n + 1]; // 存儲第一遍從頂點(diǎn)1dfs遍歷情況下的時間戳，數(shù)組下標(biāo)代表頂點(diǎn)編號侍芝，值表示第幾個訪問到（時間戳）
        int[] low = new int [n + 1]; // 表示每個頂點(diǎn)在不經(jīng)過父頂點(diǎn)能回到的最小時間戳（比較拗口研铆，大致可以理解為：根據(jù)num數(shù)組找到父節(jié)點(diǎn)，然后用dfs遍歷竭贩，能夠達(dá)到的最小時間戳）
        // 初始化low數(shù)組蚜印，比較重要
        for (i = 1; i <= n; i++) {
            low[i] = INF;
        }
        
        // 讀入m條邊
        for (i =1; i <= m; i++) {
            v1 = sc.nextInt();
            v2 = sc.nextInt();
            edges[v1][v2] = 1; // 其他都為零表示兩點(diǎn)之間不可達(dá)或者是自身
        }
        // 求num數(shù)組（每個頂點(diǎn)對應(yīng)的時間戳）
        dfs(1, edges, num, n);
        
        // 得到割點(diǎn)
        int cutPoint = judgeCutPoint(low, edges, n, num, 1);
        if (cutPoint == 0) {
            System.out.println("沒有割點(diǎn)！");
        } else {
            System.out.println("割點(diǎn)編號為： " + cutPoint);
        }
    }
    /**
     * 以當(dāng)前節(jié)點(diǎn)為起始點(diǎn)排除父節(jié)點(diǎn)的情況下深度優(yōu)先遍歷以獲取當(dāng)前點(diǎn)能訪問的最小時間戳
     * @param low 待計(jì)算留量、更新的最小訪問時間戳
     * @param child 當(dāng)前節(jié)點(diǎn)
     * @param parent 當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)（根據(jù)num矩陣來的）
     * @param edges 邊的鄰接矩陣
     * @param num 時間戳矩陣
     * @param n 頂點(diǎn)個數(shù)
     */
    public static void dfsExParent(int[] low, int child,int parent, int[][] edges, int[] num, int n) {
        int[] book = new int[n + 1]; // 用于判斷一個頂點(diǎn)是否已經(jīng)被放到棧里面去過了，避免環(huán)引起的錯誤
        Stack<Integer> search = new Stack<Integer>();
        search.push(child);
        book[child] = 1;
        while (!search.isEmpty()) {
            // 首先從棧頂去一個元素哟冬，并將這個頂點(diǎn)相連的頂點(diǎn)入棧
            int top = search.pop();
            // 用更小的時間戳替換掉
            if (num[top] < low[child]) {
                low[child] = num[top];
            }
            for (int i = 1; i <=n; i++) {
                if (i !=parent && num[top] < i && edges[top][i] == 1 && book[i] == 0) {
                    search.push(i);
                    book[i] = 1;
                }
            }
        }
    }
    /**
     * 判斷一個點(diǎn)是否是割點(diǎn)的方法
     * @param low low數(shù)組楼熄，存儲當(dāng)前節(jié)點(diǎn)在不經(jīng)過父節(jié)點(diǎn)的情況下能夠訪問節(jié)點(diǎn)的最小時間戳
     * @param edges 邊的鄰接矩陣
     * @param n 頂點(diǎn)個數(shù)
     * @param num 時間戳數(shù)組
     * @param start 起始點(diǎn)
     * @return
     */
    public static int judgeCutPoint(int[] low, int[][] edges, int n, int[] num, int start) {
        for (int i = 1; i <= n; i++) { // 依次計(jì)算節(jié)點(diǎn)i的low[i]值
            int parent = findParent(i, num, n);
            // 排除掉父節(jié)點(diǎn)的情況下，使用dfs遍歷浩峡，將遍歷到的時間戳值用更小的替換大的時間戳值可岂，不斷更新low[i]的值
            dfsExParent(low, i, parent, edges, num, parent);
            if (i != start && low[i] >= num[parent]) { // 要注意排除起始點(diǎn)，否則程序在第一個點(diǎn)處就返回了翰灾，顯然這是不對的
                return i;
            }
        }
        return 0;
    }
    /**
     * 根據(jù)時間戳數(shù)組找一個節(jié)點(diǎn)的父節(jié)點(diǎn)
     * @param i 當(dāng)前節(jié)點(diǎn)編號
     * @param num 時間戳數(shù)組
     * @param n 頂點(diǎn)個數(shù)
     * @return 正確情況下返回父節(jié)點(diǎn)的編號缕粹，如果返回為0表示出錯了！
     */
    public static int findParent(int i, int[] num, int n) {
        if (num[i] == i) {
            return i;
        } else {
            int parent = num[i] - 1; // 父節(jié)點(diǎn)的時間戳為當(dāng)前的時間戳減一
            for (int j = 1; j <= n; j++) {
                if (num[j] == parent) {
                    return j;
                }
            }
            return 0; // 是一種出錯的返回
        }
    }
    /**
     * 計(jì)算num數(shù)組的dfs方法
     * @param start 起始點(diǎn)
     * @param edges 邊數(shù)組
     * @param num num數(shù)組
     * @param n 頂點(diǎn)個數(shù)
     */
    public static void dfs(int start, int[][] edges, int[] num, int n) {
        int[] book = new int[n + 1]; // 用于判斷一個頂點(diǎn)是否已經(jīng)被放到棧里面去過了纸淮，避免環(huán)引起的錯誤
        int number = 1; // 被訪問到的編號
        Stack<Integer> search = new Stack<Integer>();
        search.push(start);
        book[start] = 1;
        while (!search.isEmpty()) {
            // 首先從棧頂去一個元素平斩，并將這個頂點(diǎn)相連的頂點(diǎn)入棧
            int top = search.pop();
            num[top] = number; // 為num數(shù)組賦值
            number++;
            for (int i = 1; i <=n; i++) {
                if (edges[top][i] == 1 && book[i] == 0) {
                    search.push(i);
                    book[i] = 1;
                }
            }
        }
    }
}

//***********實(shí)踐證明：這種存儲方式在某些情況下比較優(yōu)化，但是由于dfs便于找到下一個頂點(diǎn)咽块，最好還是用鄰接矩陣*******************
/**
 * 表示一條邊的對象
 * @author XZP
 *
 */
class Edge {
    private int v1;
    private int v2;
    public Edge(int v1, int v2) {
        this.v1 = v1;
        this.v2 = v2;
    }
    // getter
    public int getV1() {
        return v1;
    }
    public int getV2() {
        return v2;
    }
}

*********************************************************更新*******************************************************
昨天到后面沒啥效率了绘面，今早更新一下一個小bug（所以效率才是生產(chǎn)力，囧，今早三分鐘搞定揭璃，昨天實(shí)在寫的有些疲乏了）晚凿，代碼：

package cut.point;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

import javax.swing.text.AsyncBoxView.ChildState;

/**
 * "轟炸重要城市"問題：
 * 假設(shè)當(dāng)前我們擁有一個 地區(qū)的城市地圖，但是只有一個原子彈瘦馍，為了讓這顆原子彈發(fā)揮最大的效果歼秽，要阻斷這個地區(qū)各個城市中最關(guān)鍵的一個交通要塞，那么這個原子彈該投放在哪里情组？
 * 其實(shí)真有原子彈就不會考慮這么多了（~……~）燥筷，扯回正題。這種問題模型化之后呻惕，就是讓我們從一個無向連通圖中選擇一個“割點(diǎn)”荆责，去掉這個點(diǎn)之后，不再是連通圖亚脆。
 * 關(guān)鍵詞：DFS做院、割點(diǎn)、無向連通圖濒持、重要城市
 * 特殊說明：有些方法的參數(shù)比較多键耕，主要是這次不想用一些全局靜態(tài)變量來處理，所以就全部通過傳參解決柑营！
 * @author XZP
 *一組測試數(shù)據(jù)：
6 7 
1 4 
1 3 
4 2
3 2
2 5 
2 6
5 6
 */
public class BombingImportantCity {

    public static void main(String[] args) {
        int INF = 99999; // 人為設(shè)定的最大值
        Scanner sc = new Scanner(System.in);
        int i; // 游標(biāo)
        int v1, v2; //暫時存儲邊兩個頂點(diǎn)的編號
        int n = sc.nextInt(); // 頂點(diǎn)數(shù)
        int m = sc.nextInt(); // 邊的條數(shù)
//      Edge[] edges = new Edge[m + 1]; // 存儲邊的數(shù)組屈雄，下標(biāo)從1開始
        int[][] edges = new int[n + 1][n +1]; // 存放邊的鄰接矩陣
        int[] num = new int[n + 1]; // 存儲第一遍從頂點(diǎn)1dfs遍歷情況下的時間戳，數(shù)組下標(biāo)代表頂點(diǎn)編號官套，值表示第幾個訪問到（時間戳）
        int[] low = new int [n + 1]; // 表示每個頂點(diǎn)在不經(jīng)過父頂點(diǎn)能回到的最小時間戳（比較拗口酒奶，大致可以理解為：根據(jù)num數(shù)組找到父節(jié)點(diǎn)，然后用dfs遍歷奶赔，能夠達(dá)到的最小時間戳）
        // 初始化low數(shù)組惋嚎，比較重要
        for (i = 1; i <= n; i++) {
            low[i] = INF;
        }
        
        // 讀入m條邊
        for (i =1; i <= m; i++) {
            v1 = sc.nextInt();
            v2 = sc.nextInt();
            edges[v1][v2] = 1; // 其他都為零表示兩點(diǎn)之間不可達(dá)或者是自身
            edges[v2][v1] = 1; // 無向圖對稱
        }
        // 求num數(shù)組（每個頂點(diǎn)對應(yīng)的時間戳）
        dfs(1, edges, num, n, low);
        
        // 得到割點(diǎn)
        int cutPoint = judgeCutPoint(low, edges, n, num, 1);
        if (cutPoint == 0) {
            System.out.println("沒有割點(diǎn)！");
        } else {
            System.out.println("割點(diǎn)編號為： " + cutPoint);
        }
    }
    /**
     * 以當(dāng)前節(jié)點(diǎn)為起始點(diǎn)排除父節(jié)點(diǎn)的情況下深度優(yōu)先遍歷以獲取當(dāng)前點(diǎn)能訪問的最小時間戳
     * @param low 待計(jì)算站刑、更新的最小訪問時間戳
     * @param child 當(dāng)前節(jié)點(diǎn)
     * @param parent 當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)（根據(jù)num矩陣來的）
     * @param edges 邊的鄰接矩陣
     * @param num 時間戳矩陣
     * @param n 頂點(diǎn)個數(shù)
     */
    public static void dfsExParent(int[] low, int child,int parent, int[][] edges, int[] num, int n, int start) {
        int[] book = new int[n + 1]; // 用于判斷一個頂點(diǎn)是否已經(jīng)被放到棧里面去過了另伍，避免環(huán)引起的錯誤
        Stack<Integer> search = new Stack<Integer>();
        search.push(child);
        book[child] = 1;
        while (!search.isEmpty()) {
            // 首先從棧頂去一個元素，并將這個頂點(diǎn)相連的頂點(diǎn)入棧
            int top = search.pop();
            // 用更小的時間戳替換掉
            if (num[top] < low[child]) {
                low[child] = num[top];
            }
            for (int i = 1; i <=n; i++) {
                if (i !=parent && edges[top][i] == 1 && book[i] == 0) { // 不經(jīng)過父節(jié)點(diǎn)訪問其他子節(jié)點(diǎn)不等同于不訪問父節(jié)點(diǎn)＝事谩０诔ⅰ！
                    search.push(i);
                    book[i] = 1;
                }
            }
        }
    }
    /**
     * 判斷一個點(diǎn)是否是割點(diǎn)的方法
     * @param low low數(shù)組因悲，存儲當(dāng)前節(jié)點(diǎn)在不經(jīng)過父節(jié)點(diǎn)的情況下能夠訪問節(jié)點(diǎn)的最小時間戳
     * @param edges 邊的鄰接矩陣
     * @param n 頂點(diǎn)個數(shù)
     * @param num 時間戳數(shù)組
     * @param start 起始點(diǎn)
     * @return
     */
    public static int judgeCutPoint(int[] low, int[][] edges, int n, int[] num, int start) {
        for (int i = 1; i <= n; i++) { // 依次計(jì)算節(jié)點(diǎn)i的low[i]值
            int parent = findParent(i, num, n);
            // 排除掉父節(jié)點(diǎn)的情況下堕汞，使用dfs遍歷，將遍歷到的時間戳值用更小的替換大的時間戳值囤捻，不斷更新low[i]的值
            dfsExParent(low, i, parent, edges, num, n, start);
            if (low[i] >= num[parent]) { // 要注意排除起始點(diǎn)臼朗，否則程序在第一個點(diǎn)處就返回了邻寿，顯然這是不對的
                // 還要判斷是否是根節(jié)點(diǎn)
                if (parent != start) {
                    return parent;
                } else {
                    // 判斷根節(jié)點(diǎn)且至少有兩個孩子，這兩個孩子沒有其他可達(dá)到的的其他路徑的情況下才是割點(diǎn)
                    if (isRootCutPoint(edges, start, n)) {
                        return start;
                    }
                }
            }
        }
        return 0;
    }
    public static boolean isRootCutPoint(int[][] edges, int root, int n) {
        boolean flag = false;
        List<Integer> child = new ArrayList<>();
        // 計(jì)算孩子數(shù)
        for (int i = 1; i <= n; i++) {
            if (edges[root][i] == 1) {
                child.add(i);
            }
        }
        int size = child.size();
        for (int i = 0; i< size; i++) {
            for (int j = i + 1; j < size; j ++) {
                if (!isReachable(child.get(i), child.get(j), edges, n, root)) {
                    return true;
                }
            }
        }
        return flag;
    }
    public static boolean isReachable(int a, int b, int[][] edges, int n, int root) {
        int[] book = new int[n + 1]; // 用于判斷一個頂點(diǎn)是否已經(jīng)被放到棧里面去過了视哑，避免環(huán)引起的錯誤
        Stack<Integer> search = new Stack<Integer>();
        search.push(a);
        book[a] = 1;
        while (!search.isEmpty()) {
            // 首先從棧頂去一個元素绣否，并將這個頂點(diǎn)相連的頂點(diǎn)入棧
            int top = search.pop();
            if (top == b) {
                return true;
            }
            for (int i = 1; i <=n; i++) {
                if (i != root && edges[top][i] == 1 && book[i] == 0) {
                    search.push(i);
                    book[i] = 1;
                }
            }
        }
        return false;
    }
    /**
     * 根據(jù)時間戳數(shù)組找一個節(jié)點(diǎn)的父節(jié)點(diǎn)
     * @param i 當(dāng)前節(jié)點(diǎn)編號
     * @param num 時間戳數(shù)組
     * @param n 頂點(diǎn)個數(shù)
     * @return 正確情況下返回父節(jié)點(diǎn)的編號，如果返回為0表示出錯了挡毅！
     */
    public static int findParent(int i, int[] num, int n) {
        if (num[i] == i) {
            return i;
        } else {
            int parent = num[i] - 1; // 父節(jié)點(diǎn)的時間戳為當(dāng)前的時間戳減一
            for (int j = 1; j <= n; j++) {
                if (num[j] == parent) {
                    return j;
                }
            }
            return 0; // 是一種出錯的返回
        }
    }
    /**
     * 計(jì)算num數(shù)組的dfs方法
     * @param start 起始點(diǎn)
     * @param edges 邊數(shù)組
     * @param num num數(shù)組
     * @param n 頂點(diǎn)個數(shù)
     */
    public static void dfs(int start, int[][] edges, int[] num, int n, int[] low) {
        int[] book = new int[n + 1]; // 用于判斷一個頂點(diǎn)是否已經(jīng)被放到棧里面去過了蒜撮，避免環(huán)引起的錯誤
        int number = 1; // 被訪問到的編號
        Stack<Integer> search = new Stack<Integer>();
        search.push(start);
        book[start] = 1;
        while (!search.isEmpty()) {
            // 首先從棧頂去一個元素，并將這個頂點(diǎn)相連的頂點(diǎn)入棧
            int top = search.pop();
            num[top] = number; // 為num數(shù)組賦值
            low[top] = number; // 最開始就是自己
            number++;
            for (int i = 1; i <=n; i++) {
                if (edges[top][i] == 1 && book[i] == 0) {
                    search.push(i);
                    book[i] = 1;
                }
            }
        }
    }
}

//***********實(shí)踐證明：這種存儲方式在某些情況下比較優(yōu)化跪呈，但是由于dfs便于找到下一個頂點(diǎn)段磨，最好還是用鄰接矩陣*******************
/**
 * 表示一條邊的對象
 * @author XZP
 *
 */
class Edge {
    private int v1;
    private int v2;
    public Edge(int v1, int v2) {
        this.v1 = v1;
        this.v2 = v2;
    }
    // getter
    public int getV1() {
        return v1;
    }
    public int getV2() {
        return v2;
    }
}