传送门：Critical Links
题意：给出一个无向图,按顺序输出桥。
分析：模板题，求出桥后排个序输出。
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <queue> #include <cstdlib> #include <stack> #include <vector> #include <set> #include <map> #define LL long long #define mod 100000000 #define inf 0x3f3f3f3f #define eps 1e-6 #define N 10010 #define FILL(a,b) (memset(a,b,sizeof(a))) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define PII pair<int,int> using namespace std; struct edge { int v,next; edge(){} edge(int v,int next):v(v),next(next){} }e[N<<1]; struct bridge { int u,v; bridge(){} bridge(int u,int v):u(u),v(v){} bool operator<(const bridge &a)const{ if(u==a.u)return v<a.v; return u<a.u; } }b[N<<1]; int n,step,top,tot,num; int head[N],dfn[N],low[N],Stack[N]; bool instack[N],vis[N<<1]; map<int,int>mp; void init() { tot=0;step=0;top=0;num=0; FILL(head,-1);FILL(dfn,0); FILL(low,0);FILL(instack,false); FILL(vis,0);mp.clear(); } bool isHash(int u,int v) { if(mp[u*N+v])return 1; if(mp[v*N+u])return 1; mp[u*N+v]=mp[v*N+u]=1; return 0; } void addedge(int u,int v) { e[tot]=edge(v,head[u]); head[u]=tot++; } void tarjan(int u) { dfn[u]=low[u]=++step; Stack[top++]=u; instack[u]=true; for(int i=head[u];~i;i=e[i].next) { int v=e[i].v; if(vis[i])continue; vis[i]=vis[i^1]=1; if(!dfn[v]) { tarjan(v); if(low[u]>low[v])low[u]=low[v]; //桥：一条无向边(u,v)是桥，当且仅当(u,v)为树枝边，且满足DFS[u]<Low[v] if(low[v]>dfn[u]) { b[num++]=bridge(min(u,v),max(u,v)); } } else if(low[u]>dfn[v]) { low[u]=dfn[v]; } } instack[u]=false; top--; } void solve() { for(int i=0;i<n;i++) if(!dfn[i])tarjan(i); sort(b,b+num); printf("%d critical links ",num); for(int i=0;i<num;i++) printf("%d - %d ",b[i].u,b[i].v); puts(""); } int main() { int u,v; while(scanf("%d",&n)>0) { init(); for(int i=1;i<=n;i++) { int t,u,v; scanf("%d (%d)",&u,&t); while(t--) { scanf("%d",&v); if(!isHash(u,v)) { addedge(u,v); addedge(v,u); } } } solve(); } }