Bridge of undirected graph

One   The finishing touch

Time stamp ：dfn[u]  Representation node u  Sequence number of depth first traversal .

Traceability point ：low[u] Representation node u or u Our descendants can be traced back to dfn Sequence number of the smallest node , That is to return to the earliest past .

Two   give an example

At the beginning ,dfn[u]=low[u], If the adjacent node of this node is not accessed , Depth first traversal is always performed ,1-2-3-5-6-4, here 4  The adjacency point 1  Has been interviewed , And 1  No 4  Parent node ,4 The parent of is 6（ Depth first search the parent node on the tree ）.

node 4  The earliest node that can be returned is node 1（dfn=1）, therefore low[4]=min(low[4],dfn[1])=1, return , to update low[6]=min(low[6],low[4])=1. Update all ancestor nodes on the path  low  value , Because descendants can go back to the trace point , Their ancestors can also return .

3、 ... and The bridge of an undirected graph

Bridge decision rule ： No to the edge  x-y  It's a bridge , If and only if there is a node in the search tree  y, Satisfy  low[y] > dfn[x].

in other words , If the child's  low  Worth more than yourself , Then the bridge is from the node to the child's side . In the diagram above , edge 5-7 in ,5 The child node of is 7, Satisfy  low[7]>dfn[5], therefore 5-7  For the bridge .

Four   Code

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]);
    }
}

5、 ... and   test