题目描述

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

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

Return all critical connections in the network in any order.

Example 1:

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.

Constraints:

• 1 <= n <= 10^5
• n-1 <= connections.length <= 10^5
• connections[i][0] != connections[i][1]
• There are no repeated connections.

题意：力扣数据中心有n 台服务器，分别按从 0 到n-1的方式进行了编号。

它们之间以「服务器到服务器」点对点的形式相互连接组成了一个内部集群，其中连接 connections是无向的。

从形式上讲，connections[i] = [a, b]表示服务器 a 和b之间形成连接。任何服务器都可以直接或者间接地通过网络到达任何其他服务器。

「关键连接」是在该集群中的重要连接，也就是说，假如我们将它移除，便会导致某些服务器无法访问其他服务器。请你以任意顺序返回该集群内的所有 「关键连接」。

算法1

(tarjan) $O(V + E)$

题解：其实这道题让我们求的就是联通图中的桥，我们可以通过一遍DFS求出割点和桥也就是tarjan算法。

我们首先介绍一下dfs搜索树：

右图就是一个dfs搜索树，树中的边可以分为两种：

• 树边：DFS过程中访问未访问节点而引出的边 实线
• 回边：DFS过程中遇到已访问过节点的边。虚线

我们定义如下几个数组：

• dfn数组：dfn[i]代表的是第i号节点在dfs过程中的遍历顺序，可以看作是时间戳。在第一次设定后保持不变。
• low数组：low[i]代表的是第i号节点在不经过其父节点能够到达的所有节点中最小时间戳。在递归搜索的过程中不断更新

我们用cnt代表时间戳，初始时，dfn数组和low数组都相等等于cnt，假设我们从u节点开始，递归搜索其所有的子节点v，那么low数组的更新方式为：
$$low[u] = min(low[u],low[v]),如果v没有被访问过即(u,v)是树边$$
$$low[u] = min(low[u],dfn[v]),如果v已经访问过了，并且v不是u的父节点$$
桥的判定方法：如果v是未访问的节点，并且dfn[u] < low[v]，那么(u,v)是树边。

割点判断方法：如果u不是根，v是u某一个未访问子节点，只要存在dfn[u] <= low[v]，那么u就是割点；如果u是根的话，当u有两个以上子树的时候就是割点（这个可以通过判断其有几个未访问过的子节点来判断）。

class Solution {
public:
    vector<vector<int>> graph,bridges;
    vector<int> dfn,low;
    vector<int> cut;
    int root,cnt = 1;
    void tarjan(int u,int fa)
    {
        dfn[u] = cnt;
        low[u] = cnt ++;
        int child = 0;
        for(auto v : graph[u])
        {
            if(dfn[v] == 0){ //v未被访问过
                child ++;    //记录节点u的子树个数
                tarjan(v,u);
                low[u] = min(low[u],low[v]);
                if(dfn[u] < low[v]) //判断桥
                    bridges.push_back({u,v});
                if(dfn[u] <= low[v]) //判断割点,注意此处是小于等于
                {
                    if(u == root && child > 1) cut[u] = 1;
                    else if(u != root)
                        cut[u] = 1;
                }
            }else if(v != fa){ // v被访问过了并且不是u的父节点
                low[u] = min(low[u],dfn[v]);
            }
        }
    }
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        graph.resize(n);
        dfn.resize(n);
        low.resize(n);
        cut.resize(n);
        for(auto &p : connections)
        {
            graph[p[0]].push_back(p[1]);
            graph[p[1]].push_back(p[0]);
        }
        // 如果整个图是联通的话
        root = 0;
        tarjan(0,-1);
        // for(int i = 0 ; i < n ; i ++)
        //     printf("%d ",cut[i]);
        // 如果原来的图不是联通的话
        // for(int i = 0 ; i < n ; i ++)
        // {
        //     if(dfn[i] == 0)
        //     {
        //         root = i;
        //         tarjan(i,-1);
        //     }
        // }
        return bridges;
    }
};