1192. Critical Connections in a Network

Loading...LeetCode

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

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

Tarjan算法：求解图的割点与桥（割边） - nullzx - 博客园

Tarjan算法在此处的思路是：

将图作为有向连通图进行DFS，找到强连通分量。由于强连通分量内部的节点性质相同（都可以连接到该分量的起始节点），可以将一个强连通分量内的节点缩成一个点（即消除了环），这样，原图就变成了一个有向无环图 (DAG), 有向无环图的每个路径都是题目要找的 critical connections.

tarjan算法-解决有向图中求强连通分量的利器 - RunningSnail - 博客园

实现细节：

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之间不存在其他路径。

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