社区讨论

求助,为什么洛谷上能过,ACwing上连样例都过不了

P2860[USACO06JAN] Redundant Paths G参与者 3已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@mhjsffbh
此快照首次捕获于
2025/11/04 07:45
4 个月前
此快照最后确认于
2025/11/04 07:45
4 个月前
查看原帖
rt, 洛谷评测记录,同一个代码,这两个题的样例也是一样的,为什么Acwing上这个代码样例输出的是1,DEV和洛谷的都是2
CPP
#include<iostream>
#include<cmath>

using namespace std;

const int N=1e4+500;

int n,m;

struct str{
	int u,v,nxt;
}a[N],b[N];
int tot1=1,tot2=1;
int head1[N],head2[N];

int dfn[N],low[N];
int id;

int br[N];
int cnt;

int f[N];
int ans;

int c[N];
int num;

void add1(int u,int v){
	a[++tot1].v=v;
	a[tot1].u=u;
	a[tot1].nxt=head1[u];
	head1[u]=tot1;
}

void add2(int u,int v){
	b[++tot2].u=u;
	b[tot2].v=v;
	b[tot2].nxt=head2[u];
	head2[u]=tot2;
}

void tarjan(int x,int fa){
	dfn[x]=low[x]=++id;
	for(int i=head1[x];i;i=a[i].nxt){
		int y=a[i].v;
		if(y==fa) continue;
		if(!dfn[y]){
			tarjan(y,x);
			low[x]=min(low[x],low[y]);
			if(dfn[x]<low[y]){
			br[i]=br[i^1]=1;
		}
		}else{
			low[x]=min(dfn[y],low[x]);
		}
		
	}
	return ;
}

void dfs(int x){
	c[x]=num;
	for(int i=head1[x];i;i=a[i].nxt){
	    int v=a[i].v;
	    if(c[v]||br[i]) continue;
	    dfs(v);
	}
	return ;
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%ld%ld",&u,&v);
		add1(u,v);
		add1(v,u);
	}
	//cout<<tot1<<endl;
	tarjan(1,0);
	for(int i=1;i<=n;i++){
	    if(!c[i]){
	        num++;
	        dfs(i);
	    }
	}
	/*for(int i=1;i<=2*m+2;i++){
		cout<<br[i]<<endl;
	}*/
	for(int i=1;i<=tot1;i++){
		int u=a[i].u;
		int v=a[i].v;
		if(c[u]!=c[v]){
			add2(c[u],c[v]);
			add2(c[v],c[u]);
			f[c[u]]++;
			//cout<<u<<" "<<v<<endl;
		}
	}
	//cout<<tot1<<endl;
	for(int i=1;i<=num;i++){
		if(f[i]==1) ans++;
	}
	cout<<(ans+1)/2;
}

回复

4 条回复,欢迎继续交流。

正在加载回复...