6月月赛E题并查集WA90分……
题目描述：
小信有一张 n 个点 m 条边的无向图（无自环重边）。
今天小信觉得这张图有点丑，他想在这张图上连一条边（这条新的边不和原来的任何边重合），并且小信希望连完这条边之后，这张图变成一棵树。但小信不知道该怎么连边，他希望你能帮帮他。
请你输出一个整数，表示有多少条边满足小信的要求。
其中，我们称无向无环的连通图为树
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
int n,m;
int fa[N],cnt=0,sz[N];
int anc(int x) {
return fa[x]==x?x:fa[x]=anc(fa[x]);
}
void mer(int x,int y) {
int ax=anc(x),ay=anc(y);
if(ax==ay) return;
fa[ay]=ax;
sz[ax]+=sz[ay];
cnt--;
}
int main() {
freopen("202406E.in","r",stdin);
freopen("202406E.out","w",stdout);
cin >> n >> m;
for(int i = 1;i <= n;i++) fa[i] = i,sz[i] = 1;
cnt = n;
for(int i = 1;i <= m;i++) {
int x,y;
cin >> x >> y;
mer(x,y);
}
if(m!=n-2&&cnt!=2) {
cout << "0\n";
return 0;
}
int rt1=anc(1),rt2=0;
for(int i = 2;i <= n;i++) {
if(anc(i)!=rt1) {
rt2=anc(i);
break;
}
}
// cout << rt1 << ' ' << rt2 << '\n';
cout << (sz[rt1]*sz[rt2]) << '\n';
}