判断桥
代码如下:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int, int> pii;
const int max_n = 1100;
const int max_m = 1e6 + 100;
struct edge{
int to, rev,next;
}E[max_m << 1];
int head[max_n];
int cnt = 1;
void add(int from, int to,int rev) {
E[cnt].to = to;E[cnt].rev = rev;
E[cnt].next = head[from];
head[from] = cnt++;
}
int dfn[max_n], low[max_n];
int tot = 0;
bool is[max_m];
void tarjan(int u, int fa) {
dfn[u] = low[u] = ++tot;
for (int i = head[u];i;i = E[i].next) {
int v = E[i].to;
if (v == fa)continue;
if (!dfn[v]) {
tarjan(v, u);
low[u] = min(low[u], low[v]);
if (low[v] > dfn[u])
is[i] = is[E[i].rev] = true;
}
else low[u] = min(low[u], dfn[v]);
}
}
int n;
int main() {
while (scanf("%d", &n)!=EOF) {
fill(head, head + max_n, 0);cnt = 1;
fill(dfn, dfn + max_n, 0);tot = 0;
fill(low, low + max_n, 0);
for (int i = 1, u, cct, v;i <= n;++i) {
scanf("%d (%d)", &u, &cct);++u;
while (cct--) {
scanf("%d", &v);++v;
if (u > v)continue;
add(u, v, cnt + 1);add(v, u, cnt - 1);
}
}fill(is, is + cnt + 1, false);
for (int i = 1;i <= n;++i)
if (!dfn[i])
tarjan(i, i);
vector<pii> ans;
for (int u = 1;u <= n;++u) {
for (int i = head[u];i;i = E[i].next) {
edge& e = E[i];
if (e.to > u && is[i])
ans.push_back(make_pair(u, e.to));
}
}sort(ans.begin(), ans.end());
printf("%d critical links\n", ans.size());
for (int i = 0;i < ans.size();++i)
printf("%d - %d\n", ans[i].first - 1, ans[i].second - 1);
printf("\n");
}
}