WA求助
查看原帖
WA求助
673517
Network_Flow楼主2024/4/22 20:48

用的是完全图减已经给出的关系数,但是WA了接近一半。求调。

#include <iostream>
#include <cstdio>

using namespace std;
long long n, m, a[200005], fa[200005], sum[200005];
long long find(long long x){
	if(fa[x]!=x) fa[x]=find(fa[x]);
	return fa[x];
}
void add(long long x, long long y){
	long long z=find(x), u=find(y);
	fa[u]=z;
}
int main(){
	scanf("%lld%lld", &n, &m);
	for (long long i=1; i<=n; i++) fa[i]=i;
	for (long long i=1; i<=m; i++){
		long long x, y;scanf("%lld%lld", &x, &y);
		add(x, y);
	}
	for (long long i=1; i<=n; i++) sum[fa[i]]++;
	long long ans=0;
	for (long long i=1; i<=n; i++) ans+=(sum[i]*(sum[i]-1))/2;
	printf("%lld\n", ans-m);
}
2024/4/22 20:48
加载中...