无向图的桥

一 点睛

时间戳：dfn[u] 表示节点 u 深度优先遍历的序号。

追溯点：low[u]表示节点u或u的子孙能通过非父子追溯到dfn最小节点的序号，即回到最早的过去。

二 举例

初始时，dfn[u]=low[u],如果该节点的邻节点未被访问，则一直进行深度优先遍历，1-2-3-5-6-4，此时 4 的邻接点 1 已被访问，且 1 不是 4 的父节点，4 的父节点是6（深度优先搜索树上的父节点）。

节点 4 能回到最早的节点是节点1（dfn=1），因此low[4]=min(low[4],dfn[1])=1,返回时，更新low[6]=min(low[6],low[4])=1。更新路径上所有祖先节点的 low 值，因为子孙能回到的追溯点，其祖先也能回到。

三 无向图的桥

桥判定法则：无向边 x-y 是桥，当且仅当搜索树上存在一个节点 y，满足 low[y] > dfn[x]。

也就是说，如果孩子的 low 值比自己大，则从该节点到这个孩子的边为桥。在上图中，边5-7中，5的子节点为7，满足 low[7]>dfn[5],因此 5-7 为桥。

四 代码

package graph.tarjanbridge;

import java.util.Arrays;
import java.util.Scanner;

public class TarjanBridge {
    static int SIZE = 100010;
    static int head[] = new int[SIZE], to[] = new int[SIZE << 1], next[] = new int[SIZE << 1];
    static int cnt = 0;

    static void addEdge(int x, int y) {
        to[cnt] = y;
        next[cnt] = head[x];
        head[x] = cnt++;
        to[cnt] = x;
        next[cnt] = head[y];
        head[y] = cnt++;
    }

    static int dfn[] = new int[SIZE], low[] = new int[SIZE];
    static int index;
    static boolean bridge[] = new boolean[SIZE << 1];


    static void tarjan(int x, int edge) {
        dfn[x] = low[x] = ++index;
        for (int i = head[x]; i >= 0; i = next[i]) {
            int y = to[i];
            if (dfn[y] == 0) {
                tarjan(y, i);
                low[x] = Math.min(low[x], low[y]);
                if (dfn[x] < low[y])
                    bridge[i] = bridge[i ^ 1] = true;
            } else if (i != (edge ^ 1))
                low[x] = Math.min(low[x], dfn[y]);

        }
    }

    static void init() {
        Arrays.fill(head, -1);
        cnt = 0;
    }

    static int n, m;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        init();
        for (int i = 0; i < m; i++)
            addEdge(sc.nextInt(), sc.nextInt());

        for (int i = 1; i <= n; i++)
            if (dfn[i] == 0)
                tarjan(i, -1);
        for (int i = 1; i < cnt; i += 2)
            if (bridge[i])
                System.out.println(to[i ^ 1] + " " + to[i]);
    }
}

五 测试