图论(1)-tarjan算法求强联通分量，割点，桥

在LC里面的图论题，一般还是非常基础的，BFS，或者Dijkstra 为主。
造成其实有很多经典的图论算法运用的不多。也确实因为这类算法的运用是比较难的问题。
直到我遇到了1192. Critical Connections in a Network，看来也并不是完全没有。这道题本质是求一个无向图的边双连通分量，是个模板题。解法就是tarjan算法。无论是求有向图的强联通分量，还是无向图的边双连通或点双连通都可以用他的算法搞。而且时间复杂度还非常好。
所以开个专题，总结一下他的连通算法思想。

下面的分析，主要偏向实战与应用。

有向图的强连通分量

所谓连通分量，就是在一个有向图里的一组点集。这个点集里的任意2个点都可以互相通过点集的边走到对方。
那么强连通分量就是这个极大的点集。也就是说我们无法通过再添加一个点，使得该点集依然是连通分量。那么当前这个点集就是一个强连通分量。

如上图，图中圈出的3个就是3个强连通分量。其中中间那个3个点的强连通分量里的任意2个点，都是一个连通分量。

有了强连通分量，我们可以通过把每个强连通的分量给缩成一个点，那么整个图就会变成一个有向无环图。有向无环图就会有拓扑序，可以利用这个性质解一些题目。
下面是tarjan 求强连通分量的一个伪代码。

dfn[u] 是深度优先搜索遍历u时结点被搜索的次序

low[u] : 设以 u为根的子树为 subtree(u)。 low[u] 定义为以下结点的 dfn 的最小值： subtree(u) 中的结点；从 subtree(u)通过一条不在搜索树上的边能到达的结点。

一个结点的子树内结点的 dfn 都大于该结点的 dfn。

从根开始的一条路径上的 dfn 严格递增，low 严格非降。

按照深度优先搜索算法搜索的次序对图中所有的结点进行搜索。在搜索过程中，对于结点 u 和与其相邻的结点 v （v 不是 u 的父节点）考虑 3 种情况：

v 未被访问：继续对v进行深度搜索。在回溯过程中，用 low[v]更新 low[u] 。因为存在从 u 到 v 的直接路径，所以 v 能够回溯到的已经在栈中的结点，u 也一定能够回溯到。
v 被访问过，已经在栈中：即v 已经被访问过，根据 low值的定义（能够回溯到的最早的已经在栈中的结点），则用dfn[v] 更新 low[u] 。
v 被访问过，已不在在栈中：说明 v已搜索完毕，其所在连通分量已被处理，所以不用对其做操作。

TARJAN_SEARCH(int u)
    vis[u]=true
    low[u]=dfn[u]=++dfncnt
    push u to the stack
    for each (u,v) then do
        if v hasn't been search then
            TARJAN_SEARCH(v) // 搜索
            low[u]=min(low[u],low[v]) // 回溯
        else if v has been in the stack then
            low[u]=min(low[u],dfn[v])

下面给出一个JAVA 求强连通分量，可缩点的模板

    int[] dfn, low, id;
    boolean[] inStack;
    Deque<Integer> stack;
    int timestamp = 0, sccCnt = 0;
    Set<Integer>[] gra;
    void tarjan(int u) {
        dfn[u] = low[u] = ++timestamp;
        stack.push(u);
        inStack[u] = true;
        for (int v : gra[u]) {
            if (dfn[v] == 0) {
                tarjan(v);
                low[u] = Math.min(low[v], low[u]);
            } else if (inStack[v]) low[u] = Math.min(low[u], dfn[v]);
        }
        if (dfn[u] == low[u]) {
            int y;
            ++sccCnt;
            do {
                y = stack.pop();
                inStack[y] = false;
                id[y] = sccCnt;
            } while (y != u);
        }
    }
// 缩点后的有向无环图
    Set<Integer>[] dag;
    void buildDAG(int n) {
        dag = new Set[sccCnt];
        for (int i = 0; i < n; i++) {
            for (int v : gra[i]) {
                if (id[i] != id[v])
                    dag[id[i]].add(id[v]);
            }
        }
    }

强连通分量编号顺序的逆序一定是拓扑序

无向图的双连通分量

无向图里有2种连通分量。
第一种叫边双连通分量，也称为极大无桥。另一种叫点双连通分量也称为极大无割点。

桥是一条无向边，删去后，本来连通的图会变得不连通。所以在一个边的双连通分量里，不管删去哪1条边，整个图还是连通的，并且这个点集是极大的。

割点就是一个点，删去这个点和他所关联的边之后，整个图变得不连通了。这个点称为割点。点的双连通分量就是极大的不包含割点的连通块。

一个割点至少属于2个点连通分量。如下图，点B既是左半部分的点双，也是右半部分的点双。

image.png

如何找到桥

从X开始去搜Y，如果Y能到达它的祖先节点，说明有环。如果Y无论如何都走不到比X的DFN还要小的点。那么这个边就是桥。
所以一个边是桥等价于dfn[x] < low[y]

1192. Critical Connections in a Network

求桥模板

    List<List<Integer>> res = new ArrayList<>();
    List<Integer>[] graph;
    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        int[] dfn = new int[n], low = new int[n];
        // use adjacency list instead of matrix will save some memory, adjmatrix will cause MLE
        graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        // build graph
        for (int i = 0; i < connections.size(); i++) {
            int from = connections.get(i).get(0), to = connections.get(i).get(1);
            graph[from].add(to);
            graph[to].add(from);
        }
        tarjan(0, low, dfn, -1);   
        return res;
    }

    int time = 0; // time when discover each vertex
    private void tarjan(int u, int[] low, int[] dfn, int pre) {
        dfn[u] = low[u] = ++time; // discover u
        for (int v : graph[u]) {
            if (dfn[v] == 0) { // if not discovered
                tarjan(v, low, dfn, u);
                low[u] = Math.min(low[u], low[v]);
                if (low[v] > dfn[u]) {
                    // u - v is critical, there is no path for v to reach back to u or previous vertices of u
                    res.add(Arrays.asList(u, v));
                }
            } else if (v != pre) { // if v discovered and is not parent of u, update low[u], cannot use low[v] because u is not subtree of v
                low[u] = Math.min(low[u], dfn[v]);
            }
        }
    }

如果要把所有边双连通分量给缩点，只需要在TARJAN 方法进来的时候，把元素压入栈。然后当dfn[u] == low[u] 时从栈里弹出，构造出所有点的ID。
在外面对如果1条边不在一个边双连通分量里，就可以加一条边。

下面是缩点后新图模板

int[] low, dfn, id;
    Set<Integer>[] gra;
    int timestamp = 0, dccCnt = 0;
    Deque<Integer> stack = new ArrayDeque<>();
    Map<Integer, Integer> bridges;
    void tarjan(int u, int pre) {
        low[u] = dfn[u] = ++timestamp;
        stack.push(u);
        for (int v : gra[u]) {
            if (dfn[v] == 0) {
                tarjan(v, u);
                low[u] = Math.min(low[u], low[v]);
                if (dfn[u] < low[v]) {
                    bridges.put(u, v);
                    bridges.put(v, u);
                }
            } else if (v != pre) low[u] = Math.min(low[u], dfn[v]);
        }
        if (low[u] == dfn[u]) {
            int y;
            dccCnt++;
            do {
                y = stack.pop();
                id[y] = dccCnt;
            } while (y != u);
        }
    }

    Set<Integer>[] newGra;
    void buildNewGraph() {
        newGra = new Set[dccCnt];
        for (int i = 0; i < dccCnt; i++) newGra[i] = new HashSet<>();
        for (int i = 0; i < gra.length; i++) {
            for (int v : gra[i]) {
                if (bridges.getOrDefault(i, -1) == v) 
                    newGra[id[i]].add(id[v]);
            }
        }
    }

如何找割点

如果DFS序先搜到X然后由X到Y。

如果X不是根节点，且low(y) >= dfn(x)那么X是一个割点。
X是根节点，至少有2个子节点满足这样的条件， X才是割点。

Set<Integer>[] gra;
    int[] low, dfn;
    boolean[] cut;
    int timestamp = 0, cutCnt = 0, root;

    void tarjan(int u) {
        dfn[u] = low[u] = ++timestamp;
        int flag = 0;  // 当前有几个孩子是割点
        for (int v : gra[u]) {
            if (dfn[v] == 0) {
                tarjan(v);
                low[u] = Math.min(low[u], low[v]);
                if (dfn[u] <= low[v]) {
                    flag++;
                    if ((u != root || flag > 1) && !cut[u]) {
                        cut[u] = true;
                        cutCnt++;
                    }
                }
            } else low[u] = Math.min(low[u], dfn[v]);
        }
    }

那么如何找到所有点双连通分量呢？
我们要知道所有割点属于多个点双连通分量。也就是这个几个极大点集里可能含有同一个割点。

image.png

比如上面的图，左右2个点双连通分量都含有点B。如果要缩点拆图的话。我们一般会把割点单独抽取出来。然后和每个点双连通分量缩的点建立一条无向边。对于这张图缩点后如下：

image.png

下面给出，一个求出所有点双连通分量的模板. 图不要求完全连通。

Set<Integer>[] gra;
    int[] low, dfn;
    boolean[] cut;
    int timestamp = 0, cutCnt = 0, dccCnt = 0, root;
    Deque<Integer> stack;
    List<Integer>[] dcc; // 每一个点双连通分量含有的点编号
// dccCnt 代表有多少个点双连通分量
    void tarjan(int u) {
        dfn[u] = low[u] = ++timestamp;
        int flag = 0; // 记录有几个孩子是割点
        if (gra[u].isEmpty()) { // 单个点自成一个点连通分量
            dcc[++dccCnt].add(u);
            return;
        }
        for (int v : gra[u]) {
            if (dfn[v] == 0) {
                tarjan(v);
                low[u] = Math.min(low[u], low[v]);
                if (dfn[u] <= low[v]) {
                    flag++;
                    if (!cut[u] && (u != root || flag > 1)) {
                        cut[u] = true;
                        cutCnt++;
                    }
                    dccCnt++;
                    int y;
                    do {
                        y = stack.pop();
                        dcc[dccCnt].add(y);
                    } while (y != v);
 // 这里到Y很关键，因为再弹1次就会把割点U给弹出
                    dcc[dccCnt].add(u); // u 为割点， 属于多个点连通分量，所以不用出栈
                }
            } else low[u] = Math.min(low[u], dfn[v]);
        }
    }

总结

tarjan算法的核心是dfn 和 low数组。一般都是没遍历过就DFS下去，回溯上来更新LOW数组。遍历过会有不同的判断条件。在强连通里是看子节点是否在栈里。在边双连通是看这个点是否是parent。在点双连通里就是else了。
在判断桥的时候，使用dfn[u] < low[v] ，因为边双连通是parent的时候不会去更新u(见第一条）。而点双连通需要dfn[u] <= low[v]
一般要缩点建新图，都会需要用到栈来保存元素。都是刚进DFS压栈。前2个算法都是在遍历后判断low[u] == dfn[u] 来弹栈。代表这个点是整个连通分量的进入点。因为之后属于这个连通分量的点low[u] 势必会被更新的更小。不然就不连通了。
点双连通则是在发现割点后去做这件事。出栈和上面2种算法出到当前节点U不同，是到V。因为割点U要被算进多个点连通分两种。
仔细比较这3种算法。

彩蛋

HNOI2012 矿场搭建就是一道割点运用的题目。
这道题就是求出所有的点双连通分量。随后依次遍历每个分量。如果里面只有1个点，就必须设置一个出口。如果整个分量无割点，那么就可以任选2个作为出口。
如果一些分量被割点相连。那么势必有叶子分量（只含一个割点的为叶子分量）

image.png

我们只需在叶子分量这里的任一一个非割点的点建立出口即可。
AC代码 + 模板运用

import java.util.*;

class Main {
    Set<Integer>[] gra;
    int[] low, dfn;
    boolean[] cut;
    int timestamp = 0, cutCnt = 0, dccCnt = 0, root;
    Deque<Integer> stack = new ArrayDeque<>();
    List<Integer>[] dcc;
    void tarjan(int u) {
        dfn[u] = low[u] = ++timestamp;
        stack.push(u);
        int flag = 0;
        if (gra[u].isEmpty()) { // 单个点自成一个点连通分量
            dccCnt++;
            dcc[dccCnt].add(u);
            return;
        }
        for (int v : gra[u]) {
            if (dfn[v] == 0) {
                tarjan(v);
                low[u] = Math.min(low[u], low[v]);
                if (dfn[u] <= low[v]) {
                    flag++;
                    if (!cut[u] && (u != root || flag > 1)) {
                        cut[u] = true;
                        cutCnt++;
                    }
                    dccCnt++;
                    int y;
                    do {
                        y = stack.pop();
                        dcc[dccCnt].add(y);
                    } while (y != v);
                    dcc[dccCnt].add(u); // u 为割点， 属于多个点连通分量，所以不用出栈
                }
            } else low[u] = Math.min(low[u], dfn[v]);
        }
    }
    void solve() {
        Scanner sc = new Scanner(System.in);
        int idx = 0;
        while (true) {
            idx++;
            int m = sc.nextInt();
            timestamp = 0; cutCnt = 0; dccCnt = 0;
            if (m == 0) break;
            List<int[]> edges = new ArrayList<>();
            int n = 0;
            for (int i = m - 1; i >= 0; i--) {
                int a = sc.nextInt(), b = sc.nextInt();
                edges.add(new int[]{a,b});
                n = Math.max(n, Math.max(a, b));
            }
            gra = new Set[n + 1]; dcc = new List[n + 1];
            for (int i = 1; i <= n; i++) {
                gra[i] = new HashSet<>();
                dcc[i] = new ArrayList<>();
            }
            for (int[] e : edges) {
                gra[e[0]].add(e[1]);
                gra[e[1]].add(e[0]);
            }
            low = new int[n + 1]; dfn = new int[n + 1]; cut = new boolean[n + 1];
            for (root = 1; root <= n; root++) {
                if (dfn[root] == 0)
                    tarjan(root);
            }
            long cnt = 0, ans = 1;
            for (int i = 1; i <= dccCnt; i++) {
                if (dcc[i].size() == 1) {
                    cnt++;
                } else {
                    int cutNum = 0, size = dcc[i].size();
                    for (int j : dcc[i]) if (cut[j]) cutNum++;
                    if (cutNum == 0) {
                        ans *= size * (size - 1) / 2;
                        cnt += 2;
                    } else if (cutNum == 1) {
                        cnt += 1;
                        ans *= size - 1;
                    }
                }
            }
            System.out.println("Case " + idx + ": " + cnt + " " + ans);
        }
    }
    public static void main(String[] args) {
        new Main().solve();
    }
}