同割點問題（參見我的上一篇博客）類似，割點問題（也叫關(guān)鍵橋問題）描述的是在無向圖中，倘若去掉某條邊之后，原連通圖被分割為兩個不可達的圖，則該條邊就是所謂的割邊。跟割點唯一不同的就是原本low[v] >= num[u]的判定條件變?yōu)榱薼ow[v] > num[u]，也就是要滿足子節(jié)點v現(xiàn)在連父節(jié)點u都不能到達，那么兩節(jié)點組成的邊就是割邊！代碼：

package cut.edge;

import java.util.Scanner;

/**
 * "轟炸重要橋"問題：
 * 關(guān)鍵詞：DFS、割邊、無向連通圖、關(guān)鍵橋
 * @author XZP
 *一組測試數(shù)據(jù)：
6 6 
1 4 
1 3 
4 2
3 2
2 5 
5 6
 */
public class BombingImportantBridge {
    public static int index; // 時間戳
    public static void main(String[] args) {
        int INF = 99999; // 人為設定的最大值
        int i, j; // 游標
        int v1, v2; // 暫存頂點編號
        int root; // 根節(jié)點的編號
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 頂點數(shù)
        int m = sc.nextInt(); // 邊的條數(shù)
        // 存儲邊的數(shù)組
        int[][] edges = new int[n + 1][n + 1];
        int[] num = new int[n + 1]; // 存儲第一遍dfs遍歷的時間戳
        int[] low = new int[n + 1]; // 存儲最小時間戳的數(shù)組
        // 輸入邊的信息
        for (i = 1; i<= m; i++) {
            v1 = sc.nextInt();
            v2 = sc.nextInt();
            edges[v1][v2] = 1;
            edges[v2][v1] = 1;
        }
        root = 1;
        dfs(1, root, low, num, n, edges);
        
    }
    /**
     * 深度優(yōu)先求“割邊”
     * @param child
     * @param father
     * @param low
     * @param num
     * @param n
     * @param edges
     */
    public static void dfs(int child, int father, int[] low, int[] num, int n, int[][] edges) {
        int i, j;
        index++;
        num[child] = index;
        low[child] = index;
        for (i = 1; i <= n; i++) {
            if (edges[child][i] == 1) {
                if (num[i] == 0) {
                    dfs(i, child, low, num, n, edges);
                    low[child] = min(low[i], low[child]);
                    if (low[i] > num[child]) { // 關(guān)鍵步驟，跟割點差不多，只是這里沒有等號，表示不經(jīng)過父節(jié)點，該點就不能達到祖先（包括父節(jié)點）那兩點組成的邊即割邊
                        System.out.println("割邊為 " + child + " - " + i);
                    }
                } else if (i != father) {
                    low[child] = min(low[child], num[i]);
                }
            }
        }
    }
    /**
     * 求兩個數(shù)中的較小值
     * @param a
     * @param b
     * @return
     */
    public static int min(int a, int b) {
        return a > b ? b : a;
    }
}

//***********實踐證明：這種存儲方式在某些情況下比較優(yōu)化，但是由于dfs便于找到下一個頂點，最好還是用鄰接矩陣*******************
/**
 * 表示一條邊的對象
 * @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;
    }
}