在一个几乎类似的题上(只是输入输出不同),新写了一份代码怎么也过不不去,用原来的代码直接能过。但找不出两者差异。
原(WA)
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=100100;
struct Node{
int from,to,next;
}e[maxn*2];
int N,M,head[maxn],num=0,ans;
int dfn[maxn],low[maxn],Tim=0;
bool cut[maxn];
void edged(int from,int to){
e[++num].from=from;
e[num].to=to;
e[num].next=head[from];
head[from]=num;
}
void Tarjan(int fa,int u){
dfn[u]=low[u]=++Tim;
int son=0;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(!dfn[v]){
Tarjan(u,v);
son++;
low[u]=min(low[u],low[v]);
if(fa&&low[v]>=dfn[u]) cut[u]=1;
}
else low[u]=min(low[u],dfn[v]);
}
if(!fa&&son>1) cut[u]=1;
}
int main(){
scanf("%d",&N);
int x,y;
while(scanf("%d%d",&x,&y)!=EOF){
edged(x,y);
edged(y,x);
}
for(int i=1;i<=N;i++)
if(!dfn[i]) Tarjan(0,i);
for(int i=1;i<=N;i++)
if(cut[i]) ans++;
printf("%d\n",ans);
for(int i=1;i<=N;i++)
if(cut[i]) printf("%d\n",i);
return 0;
}
新(AC)
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=10010;
int N,M,head[maxn],nume=0,dfn[maxn],low[maxn],tm=0,cut[maxn],cnum=0;
struct node{int to,nxt;}e[maxn];
void edgen(int from,int to){
e[++nume].nxt=head[from];
head[from]=nume;
e[nume].to=to;
}
void tarjan(int fa,int u){
// printf("tarjan %d\n",su);
dfn[u]=low[u]=++tm;
int son=0;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(!dfn[v]){
tarjan(u,v);
son++;
low[u]=min(low[u],low[v]);
if(fa&&low[u]>=dfn[u]) cut[u]=1;
}
else low[u]=min(low[u],dfn[v]);
}
if(!fa&&son>1) cut[u]=1;
}
int main(){
scanf("%d",&N);int x,y;
while(scanf("%d%d",&x,&y)!=EOF) edgen(x,y),edgen(y,x);
// for(int i=1;i<=N;i++)
// for(int j=head[i];j;j=e[j].nxt)
// printf("%d->%d\n",i,e[j].to);
for(int i=1;i<=N;i++)
if(!dfn[i]) tarjan(0,i);
for(int i=1;i<=N;i++)
if(cut[i]) cnum++;
printf("%d\n",cnum);
for(int i=1;i<=N;i++)
if(cut[i]) printf("%d\n",i);
return 0;
}