# 1192. Critical Connections in a Network

{% embed url="<https://leetcode.com/problems/critical-connections-in-a-network/>" %}

暴力解法就是挨个边剔除，看连通数有没有变，复杂度在O(n\*\*2)以上，显然不行。

事实上这题是在求图的割点/割边(bridge)，核心问题是找环（环内的路径任意切掉一条，都不影响环内任意节点间继续相互连通），不在任何环里的 edge 就是 bridge，找环要用到 `Tarjan算法`（不愧hard题，图论已经忘光了）：

{% embed url="<https://www.cnblogs.com/nullzx/p/7968110.html>" %}

`Tarjan算法`在此处的思路是：

将图作为`有向连通图`进行DFS，找到`强连通分量`。由于`强连通分量`内部的节点性质相同（都可以连接到该分量的起始节点），可以将一个`强连通分量`内的节点缩成一个点（即消除了环），这样，原图就变成了一个`有向无环图` ([DAG](https://zh.wikipedia.org/zh-hans/%E6%9C%89%E5%90%91%E6%97%A0%E7%8E%AF%E5%9B%BE)), `有向无环图`的每个路径都是题目要找的 critical connections.

{% embed url="<https://www.cnblogs.com/tgycoder/p/5048898.html>" %}

实现细节：

1. 确保每个点都在 tarjan DFS 中被遍历过了。
2. 判断DFS搜到底了：成环（搜到visited node）即搜到底了，回头找下一个child继续。
3. 判断记录结果，需要割点/割边一起解释：\
   **割点**：判断点u是否为割点，如果存在child node v 满足**low\[v] >= dnf\[u]** ，就说明 v 访问 u 的祖先顶点，必须通过顶点 u，而**不存在顶点 v 到 u 祖先顶点的其它路径**，所以顶点 u 就是一个割点。\
   **割边**：low\[v] > dnf\[u] 就说明 v-u 是桥，v-u之间不存在其他路径。

```python
class Solution:
    def __init__(self):
        self.time = 0
        
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        res = []
        dfn, low = [-1 for _ in range(n)], [-1 for _ in range(n)]
        parent, children = [-1 for _ in range(n)], [[] for _ in range(n)]
        
        def tarjan(u):
            dfn[u] = self.time
            low[u] = self.time
            self.time += 1
            for v in children[u]:
                # 遇到访问过的node，即搜到底，不继续往下了
                if dfn[v] >= 0: 
                    # 因为原图是无向图，所以得考虑回头访问到 parent node 的情况
                    # 如果不是 parent node，那还得更新下 low
                    if v!= parent[u]:
                        low[u] = min(low[u], dfn[v])
                    continue
                
                # unvisited
                else: 
                    parent[v] = u
                    tarjan(v) # 继续DFS
                    low[u] = min(low[v], low[u]) # 向上传递 low
                    if low[v] > dfn[u]: # 判断记录结果，u-v间不存在其他路径
                        res.append([u,v])
        
        # 遍历 parent-children 关系
        for i, j in connections:
            children[i].append(j)
            children[j].append(i)
        
        # 确保每个点都在 tarjan DFS 中被遍历过了
        for p in range(n):
            if dfn[p] < 0:
                tarjan(p)
                
        return res
```
