传送门: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<<];
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<<];
int n,step,top,tot,num;
int head[N],dfn[N],low[N],Stack[N];
bool instack[N],vis[N<<];
map<int,int>mp;
void init()
{
tot=;step=;top=;num=;
FILL(head,-);FILL(dfn,);
FILL(low,);FILL(instack,false);
FILL(vis,);mp.clear();
}
bool isHash(int u,int v)
{
if(mp[u*N+v])return ;
if(mp[v*N+u])return ;
mp[u*N+v]=mp[v*N+u]=;
return ;
}
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^]=;
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=;i<n;i++)
if(!dfn[i])tarjan(i);
sort(b,b+num);
printf("%d critical links\n",num);
for(int i=;i<num;i++)
printf("%d - %d\n",b[i].u,b[i].v);
puts("");
}
int main()
{
int u,v;
while(scanf("%d",&n)>)
{
init();
for(int i=;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();
}
}