[UVA796] Critical Links
2017年10月19日给你一个网络要求这里面的桥。
无向图中的桥就是指删除图中的某条边后连通分量增加.
#include <bits/stdc++.h>
using namespace std;
const int N = 10005;
vector<int> G[N];
vector<pair<int, int> > ans;
int low[N], dfn[N];
int dfs_clock;
void dfs(int u, int fa)
{
low[u] = dfn[u] = ++dfs_clock;
for (auto v : G[u]) {
if (!dfn[v]) {
dfs(v, u);
low[u] = min(low[u], low[v]);
if (low[v] > dfn[u]) {
ans.push_back(make_pair(min(u, v), max(u, v)));
}
} else if (v != fa) {
low[u] = min(low[u], dfn[v]);
}
}
}
int main()
{
int n;
while (~scanf("%d", &n)) {
for (int i = 0; i < n; i++) {
G[i].clear();
}
for (int i = 0; i < n; i++) {
int u, v, k;
scanf("%d (%d)", &u, &k);
while (k--) {
scanf("%d", &v);
G[u].push_back(v);
G[v].push_back(u);
}
}
ans.clear();
dfs_clock = 0;
memset(dfn, 0, sizeof(dfn));
for (int i = 0; i < n; i++) {
if (!dfn[i])
dfs(i, -1);
}
sort(ans.begin(), ans.end());
printf("%d critical links\n", ans.size());
for (auto v: ans) {
printf("%d - %d\n", v.first, v.second);
}
puts("");
}
return 0;
}