题目描述
数据中心有 n
台服务器,分别按从 0
到 n-1
的方式进行了编号。
它们之间以“服务器到服务器”点对点的形式相互连接组成了一个内部集群,其中连接 connections
是无向的。
从形式上讲,connections[i] = [a, b]
表示服务器 a
和 b
之间形成连接。任何服务器都可以直接或者间接地通过网络到达任何其他服务器。
“关键连接”是在该集群中的重要连接,也就是说,假如我们将它移除,便会导致某些服务器无法访问其他服务器。
请你以任意顺序返回该集群内的所有“关键连接”。
样例
输入:n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
输出:[[1,3]]
解释:[[3,1]] 也是正确的。
限制
1 <= n <= 10^5
n-1 <= connections.length <= 10^5
connections[i][0] != connections[i][1]
- 不存在重复的连接
算法
(tarjan求桥) $O(n + m)$
- 此题是求桥的模板题,可以去网上搜索相关文章。
- 也可以参考 AcWing的分享 。
时间复杂度
- 每个点和边仅遍历一次,故时间复杂度为 $O(n + m)$。
空间复杂度
- 需要额外数组重构图,以及存储时间戳和最小时间戳,故空间复杂度为 $O(n + m)$。
C++ 代码
class Solution {
public:
vector<int> dfn, low;
vector<vector<int>> ans;
vector<vector<int>> graph;
int counter;
void tarjan(int x, int fa) {
dfn[x] = low[x] = ++counter;
bool flag = false;
for (int y : graph[x]) {
if (!dfn[y]) {
tarjan(y, x);
low[x] = min(low[x], low[y]);
if (dfn[x] < low[y])
ans.push_back({x, y});
} else {
if (y == fa) { // 如果存在重边,则我们需要注意判断是否存在非父子边的回向边。
if (flag)
low[x] = min(low[x], dfn[y]);
flag = true;
} else {
low[x] = min(low[x], dfn[y]);
}
}
}
}
vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
graph.resize(n);
for (const auto &p : connections) {
graph[p[0]].push_back(p[1]);
graph[p[1]].push_back(p[0]);
}
dfn.resize(n, 0);
low.resize(n, 0);
counter = 0;
for (int i = 0; i < n; i++)
if (!dfn[i])
tarjan(i, -1);
return ans;
}
};
https://www.cnblogs.com/nullzx/p/7968110.html
这篇讲的很清楚