这是在kuangbin的题目里看到的，不得不吐槽一下，题目中居然没给出数据范围，还是我自己猜的～本来是一道挺裸的题，但是我wa了好多次，原因就是这里面有两个坑点，1重边特判，2输出时左边必须比右边小。
但是我之前说过，在判断割边的时候只需要直接记录就可以了，因为每条边只会访问一次，但其实这是取决于建图方式的，题目中给出了每个点都与之相连的点，所以我们建出的边一定会有重复的，所以需要用map去重一下，可以在建图的时候就判断（因为没有多重边），也可以在收集割边的时候判断。代码如下：
#include<map>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
map<int,int>ma;
#define maxn 10010
struct EDGE
{
int to,nxt;
} edge[*maxn];
int tot,n,dfn[maxn],low[maxn],head[maxn],all,resnum;
void add_edge(int u,int v)
{
edge[tot].to = v;
edge[tot].nxt = head[u];
head[u] = tot++;
}
void init()
{
memset(low,,sizeof(low));
memset(dfn,,sizeof(dfn));
all = ;
resnum = ;
ma.clear();
}
bool mul(int u,int v)
{
if(ma[u*maxn+v] || ma[v*maxn+u]) return true;
ma[u*maxn+v] = ma[v*maxn+u] = ;
return false;
}
struct Node
{
int x,y;
};
Node out[maxn];
void tarjan(int u,int fa)
{
dfn[u] = low[u] = ++all;
for(int i = head[u]; i != -; i = edge[i].nxt)
{
int v = edge[i].to;
if(!dfn[v])
{
tarjan(v,u);
low[u] = min(low[u],low[v]);
if(low[v] > dfn[u])
{
if(!mul(u,v))
{
int tmpu = u,tmpv = v;
if(tmpu > tmpv)
swap(tmpu,tmpv);
out[resnum].x = tmpu;
out[resnum].y = tmpv;
resnum++;
}
}
}
else if(v != fa) low[u] = min(low[u],dfn[v]);
}
return ;
}
bool cmp(Node a,Node b)
{
if(a.x != b.x) return a.x < b.x;
}
int getnum(char *a)
{
int lena = strlen(a);
int num = ,jw = ;
for(int i = ; i < lena; i++)
{
if(a[i] == ')')
{
for(int j = i-; j > ; j--)
{
num += (a[j]-'')*jw;
jw *= ;
}
// cout<<"num = "<<num<<endl;
return num;
}
}
}
int main()
{
int ans,m,x,y;
while(~scanf("%d",&n))
{
tot = ;
memset(head,-,sizeof(head));
for(int i = ; i < n; i++)
{
scanf("%d",&x);
char op[];
scanf("%s",op);
int m = getnum(op);
for(int j = ; j < m; j++)
{
scanf("%d",&y);
add_edge(x,y);
add_edge(y,x);
}
}
init();
for(int i = ; i < n; i++)
{
if(!dfn[i]) tarjan(i,-);
}
sort(out,out+resnum,cmp);
printf("%d critical links\n",resnum);
for(int i = ; i < resnum; i++)
{
printf("%d - %d\n",out[i].x,out[i].y);
}
puts("");
}
return ;
}