这是在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[10*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,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); all = 0; resnum = 0; 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] = 1; 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 != -1; 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 = 0,jw = 1; for(int i = 1; i < lena; i++) { if(a[i] == ')') { for(int j = i-1; j > 0; j--) { num += (a[j]-'0')*jw; jw *= 10; } // cout<<"num = "<<num<<endl; return num; } } } int main() { int ans,m,x,y; while(~scanf("%d",&n)) { tot = 0; memset(head,-1,sizeof(head)); for(int i = 0; i < n; i++) { scanf("%d",&x); char op[220]; scanf("%s",op); int m = getnum(op); for(int j = 0; j < m; j++) { scanf("%d",&y); add_edge(x,y); add_edge(y,x); } } init(); for(int i = 0; i < n; i++) { if(!dfn[i]) tarjan(i,-1); } sort(out,out+resnum,cmp); printf("%d critical links ",resnum); for(int i = 0; i < resnum; i++) { printf("%d - %d ",out[i].x,out[i].y); } puts(""); } return 0; }