1192. Critical Connections in a Network¶
题目信息¶
- 题号:
1192
- 难度:
Hard
- 主题:
无向图、桥、深度优先搜索
- 原题:
- 重点:
网络初始连通;若删除某条无向边会使至少两个服务器无法互相到达,该边就是关键连接
题目重述¶
有 n 个服务器,编号为 0 到 n - 1。数组 connections 给出无向连接,每项 [a,b] 表示服务器 a 与 b 之间存在一条边。输入网络保证整体连通。
若移除某条连接后,网络不再连通,则该连接是关键连接。请返回全部关键连接,边的顺序及每条边内部两个端点的顺序均不限。
2 <= n <= 10^5,n - 1 <= connections.length <= 10^5;不存在自环或重复边,所有端点编号合法。
自建示例¶
两个环之间的唯一连接是桥:
输入:n = 6, connections = [[0,1],[1,2],[2,0],[2,3],[3,4],[4,5],[5,3]]
输出:[[2,3]]
解释:两侧各自形成环,只有边 [2,3] 连接两个部分;删除它会使网络断开。
树中的每条边都是关键连接:
输入:n = 3, connections = [[0,1],[1,2]]
输出:[[0,1],[1,2]]
解释:树没有替代路径,删除任意一条边都会使网络不连通。