1192. Critical Connections in a Network

题目信息

题号:

1192

难度:

Hard

主题:

无向图、桥、深度优先搜索

原题:

LeetCode 1192

重点:

网络初始连通;若删除某条无向边会使至少两个服务器无法互相到达,该边就是关键连接

题目重述

有 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]]
解释:树没有替代路径,删除任意一条边都会使网络不连通。