用的是完全图减已经给出的关系数,但是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);
}