1192. Critical Connections in a Network

Question

There are n servers numbered from 0 to n - 1 connected by undirected server-to-server connections forming a network where connections[i] = [a<sub>i</sub>, b<sub>i</sub>] represents a connection between servers a<sub>i</sub> and b<sub>i</sub>. Any server can reach other servers directly or indirectly through the network.

A critical connection is a connection that, if removed, will make some servers unable to reach some other server.

Return all critical connections in the network in any order.

Solution

参考：# 60 分钟搞定图论中的 Tarjan 算法

根据connections建立图（采用数组记录图速度比用哈希表实现快）。
然后采用Tarjon算法寻找图中的桥。

时间戳

按访问顺序为数组dfn[]添加顺序。
(dfn = depth first (traversal) number)

搜索树

在无向图中，每一次从u节点出发进行DFS搜索，每个节点只访问一次，所有被访问过的节点与边构成一棵树，称之为“无向连通图的搜索树”

追溯值

数组low[]记录从当前节点u出发时，能够访问到的所有节点中，时间戳最小的值。

无向图的桥的判定法则

在一张无向图中，判断边 e （其对应的两个节点分别为 u 与 v）是否为桥，需要其满足如下条件即可：dfn[u] < low[v]

Code

class Solution {
    int num;
    int[] visited;
    int[] dfn;
    int[] low;
    List<List<Integer>> ret;
    List<Integer>[] graph;
    
    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        num = 0;
        ret = new ArrayList<>();
        visited = new int[n];
        dfn = new int[n];
        low = new int[n];
        graph = new ArrayList[n];
        
        buildGraph(n, connections);
        tarjan(0, -1);
        
        return ret;

    }
    
    private void tarjan(int u, int parent){
        dfn[u] = low[u] = num++;    //记录节点遍历的顺序并初始化low值
        visited[u] = 1;
        for(Integer v : graph[u]){
            if(v == parent) continue;
            if(visited[v] == 0){    //搜索未搜索过的相邻节点
                tarjan(v, u);
                low[u] = Math.min(low[u], low[v]);  //搜索相邻节点后，更新访问的最小值
                if(dfn[u] < low[v]){    //满足桥的定义时添加结果
                    List<Integer> e = new ArrayList<>();
                    e.add(u);
                    e.add(v);
                    ret.add(e);
                }
            }
            else{
                low[u] = Math.min(low[u], dfn[v]);  //如果搜索过相邻节点，则判断这两个值得最小值并更新
            }
        }
    }
    
    private void buildGraph(int n, List<List<Integer>> connections){
        for(int i = 0; i < n; i++){
            graph[i]=new ArrayList<>();
        }
        
        for(List<Integer> e : connections){
            int v1 = e.get(0);
            int v2 = e.get(1);
            graph[v1].add(v2);
            graph[v2].add(v1);
        }
    }
}