Critical Links

判断桥

代码如下：

#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");
    }
}