这道题就是要求桥的个数。
那么桥相应的也有判定的定理：
在和u相邻的节点中，存在一个节点是最小的时间戳都比
当前u的访问次序要大，也就是说这个点是只能通过果u到达，那么
他们之间相邻的边就是的桥
#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
using namespace std;
const int SIZE = ;
struct node{
int u,v;
}brige[SIZE];
int head[SIZE],ver[SIZE*],Next[SIZE*];
int dfn[SIZE],low[SIZE],n,m,tot,num,cnt;
void add(int x,int y){
ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}
void tarjan(int u,int pre){
dfn[u]=low[u]=++num;
for (int i=head[u];i;i=Next[i]){
int v=ver[i];
if (v==pre)continue;
if (!dfn[v]){
tarjan(v,u);
low[u]=min(low[u],low[v]);
if (low[v]>dfn[u]){
/*
在和u相邻的节点中，存在一个节点是最小的时间戳都比
当前u的访问次序要大，也就是说这个点是只能通过果u到达，那么
他们之间相邻的边就是的桥
*/
cnt++;
brige[cnt].u=u;
brige[cnt].v=v;
if (brige[cnt].u>brige[cnt].v){
swap(brige[cnt].u,brige[cnt].v);
}
}
}
else if (low[u]>dfn[v])
low[u]=min(low[u],dfn[v]);
}
}
void init(){
memset(brige,,sizeof(brige));
memset(low,,sizeof(low));
memset(ver,,sizeof(ver));
memset(dfn,,sizeof(dfn));
memset(Next,,sizeof(Next));
memset(head,,sizeof(head));
cnt=;
num=;
tot=;
}
bool cmp(node a,node b){
if (a.u==b.u)return a.v<b.v;
return a.u<b.u;
}
int main(){
int id,tmp,nx;
while(~scanf("%d",&n)){
if (n==){
printf("0 critical links\n\n");
continue;
}
init();
for(int i=;i<=n;i++){
scanf("%d",&id);
id++;
getchar();
getchar();
scanf("%d",&tmp);
getchar();
for (int j=;j<=tmp;j++){
scanf("%d",&nx);
nx++;
add(id,nx);
add(nx,id);
}
}
for (int i=;i<=n;i++){
if(!dfn[i])tarjan(i,i);
}
printf("%d critical links\n",cnt);
sort(brige+,brige++cnt,cmp);
for (int i=;i<=cnt;i++){
printf("%d - %d\n",brige[i].u-,brige[i].v-);
}
printf("\n"); }
return ;
}
/*
3 critical links
0 - 1
3 - 4
6 - 7 */