Uva 796 Critical Links 找桥

这个题很简单,但是输入有毒,用字符串的我一直RE

然后换成这样瞬间AC

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <vector>
#include <stack>
using namespace std;
typedef long long LL;
const int N = 1e4+;
int head[N],tot,n,cnt;
struct Edge{
int u,v,next;
bool operator<(const Edge& rhs)const{
if(u!=rhs.u)return u<rhs.u;
return v<rhs.v;
}
}edge[N*],o[N*];
void add(int u,int v){
edge[tot].v=v;
edge[tot].next=head[u];
head[u]=tot++;
}
int dfn[N],low[N],clk;
void targin(int u,int f){
dfn[u]=low[u]=++clk;
for(int i=head[u];~i;i=edge[i].next){
int v=edge[i].v;
if(v==f)continue;
if(!dfn[v]){
targin(v,u);
low[u]=min(low[u],low[v]);
if(dfn[u]<low[v]){
++cnt;
o[cnt].u=min(u,v);
o[cnt].v=max(u,v);
}
}
else if(dfn[v]<low[u])low[u]=dfn[v];
}
}
int main(){
while(~scanf("%d",&n)){
memset(head,-,sizeof(head));
cnt=clk=tot=;
for(int i=;i<=n;++i){
int u,k;
scanf("%d (%d)",&u,&k);
while(k--){int v;scanf("%d",&v);add(u,v);}
}
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
for(int i=;i<n;++i)
if(!dfn[i])targin(i,-);
printf("%d critical links\n",cnt);
if(cnt)sort(o+,o++cnt);
for(int i=;i<=cnt;++i){
printf("%d - %d\n",o[i].u,o[i].v);
}
printf("\n");
}
return ;
}
上一篇:最优化WPF 3D性能(基于“Tier-2”硬件)


下一篇:微信开放平台 公众号第三方平台开发 教程三 一键登录授权给第三方平台