无向连通图中，如果删除某边后，图变成不连通，则称该边为桥。
也可以先用Tajan()进行dfs算出所有点 的low和dfn值，并记录dfs过程中每个 点的父节点；然后再把所有点遍历一遍， 看其low和dfn,满足dfn[ fa ]<low[ i ]（0<i<=n, i 的 father为fa） —— 则桥为fa-i。 找桥的时候，要注意看有没有重边；有重边，则不是桥。
另外，本题的题意及测试样例中没有重边，所以不用考虑重边。
带详细注释的题解：
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<stack>
#include<vector>
#define maxn 10010
using namespace std;
int dfn[maxn],low_link[maxn] ,Father[maxn];
//tarjan 算法的dfn ——在DFS过程中 的访问序号(也可以叫做开始时间
//tarjan 算法的low_link[i]——从i节点出发DFS过程中i下方节点所能到达的最早的节点的 开始时间
int bridgenum, Time ,n ; //桥的总数，dfn时间戳，n为顶点数，
vector<int>G[maxn]; //定义图的邻接矩阵表
stack<int>st;
struct node{
int u,v;
}bridge[maxn]; //整个图的桥的存储
bool cmp( node a,node b )
{
if(a.u!=b.u)return a.u<b.u;
else return a.v<b.v;
}
void init(){
int i;
for(i=;i<=n;i++) //初始化邻接表
G[i].clear();
bridgenum=;Time=;
memset(dfn,,sizeof(dfn));
memset(low_link,,sizeof(low_link));
memset(Father,,sizeof(Father));
}
void tarjan(int u,int fa)
{
low_link[u]=dfn[u]=++Time;
Father[u]=fa; //记录父节点
// st.push(u);
for(int i=;i<(int)G[u].size();i++){
int v=G[u][i];
if(!dfn[v]){
tarjan(v,u);
low_link[u]=min(low_link[u],low_link[v]);
}
else if(v!=fa){ //不能连接到父节点！
low_link[u]=min(low_link[u],dfn[v]);
}
else{
//这种情况就是有重边的情况！不予处理，直接跳过！
}
}
}
void solve()
{
for(int i=;i<n;i++){
if(!dfn[i])
tarjan(i,-);
}
int ans=;
for(int i=;i<n;i++){
int v=Father[i];
if(dfn[v]<low_link[i]&&v!=-){ //若v-i可以构成父节点
bridge[ans].u=v; //桥的两条边
bridge[ans].v=i;
if(bridge[ans].u>bridge[ans].v)
swap(bridge[ans].u,bridge[ans].v);
ans++;
}
}
sort(bridge,bridge+ans,cmp);
printf("%d critical links\n",ans);
for(int i=;i<ans;i++){
printf("%d - %d\n",bridge[i].u,bridge[i].v);
}
}
int cal_num(char ch[]){
int len=strlen(ch),s=;
for(int i=;i<=len-;i++){
s=s*+ch[i]-'';
}
return s;
}
int main()
{
int T,cas=;
scanf("%d",&T);
while(T--)
{
init();
char ch[];
int m ,u,v; //边数
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d%s",&u,ch);
m=cal_num(ch); //截取出数字存入m——边数
for(int j=;j<=m;j++){
scanf("%d",&v);
G[u].push_back(v); //这里按单向边任意一边存储就可以了，毕竟是无向图！
G[v].push_back(u);
}
}
printf("Case %d:\n",++cas);
solve();
}
return ;
}