求看这两份代码有什么不一样
查看原帖
求看这两份代码有什么不一样
142549
hbhz_zcy楼主2022/1/25 20:14

在一个几乎类似的题上(只是输入输出不同),新写了一份代码怎么也过不不去,用原来的代码直接能过。但找不出两者差异。
原(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;
}
2022/1/25 20:14
加载中...