lightoj 1026 无向图 求桥

题目链接:http://lightoj.com/volume_showproblem.php?problem=1026

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int maxn = ;
const int INF = 0x3f3f3f; vector<int> G[maxn];
int pre[maxn],dfs_clock,low[maxn]; struct ANS{
int l,r;
bool operator < (const ANS& a) const{
return l < a.l || (l == a.l && r < a.r); //排序被坑了,WA了好几次啊,没想后面的情况。
}
}ans[maxn];
int cnt;
int n; void tarjan(int u,int fa){
low[u] = pre[u] = dfs_clock++;
for(int i=;i<G[u].size();i++){
int v = G[u][i];
if(v == fa) continue;
if(!pre[v]){
tarjan(v,u);
low[u] = min(low[u],low[v]);
if(low[v] > pre[u]){
ans[cnt].l = min(u,v);
ans[cnt].r = max(u,v);
cnt++;
}
}
else
low[u] = min(low[u],pre[v]);
}
} void init(){
cnt = ;
dfs_clock = ;
memset(pre,,sizeof(pre));
for(int i=;i<n;i++) G[i].clear();
}
int main()
{
freopen("E:\\acm\\input.txt","r",stdin);
int T;
cin>>T;
for(int t=;t<=T;t++){
scanf("%d",&n);
init();
for(int i=;i<n;i++){
int u,m;
scanf("%d (%d)",&u,&m);
for(int j=;j<=m;j++){
int v;
scanf("%d",&v);
G[u].push_back(v);
}
}
for(int i=;i<n;i++){
if(!pre[i]){
tarjan(i,-);
}
}
printf("Case %d:\n",t);
printf("%d critical links\n",cnt);
sort(ans,ans+cnt);
for(int i=;i<cnt;i++){
printf("%d - %d\n",ans[i].l,ans[i].r);
}
}
}
上一篇:[Unit Testing] Angular Test component with required


下一篇:hdu 4983 Goffi and GCD(欧拉函数)