蓝桥杯合根植物并查集

Question

原题洛谷：https://www.luogu.com.cn/problem/P8654
考点：并查集
套了并查集模板，在join函数中用cnt--记录总集合数量变化最后输出cnt，不知道为什么样例过了最后全WA

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

int m,n,k;
int pre[1000005],rankk[1000005]={0},cnt;

int find(int x){
    if(pre[x]=x)return x;
    return pre[x]=find(pre[x]);
}

void join(int x,int y)             
{
    x=find(x),y=find(y);          
    if(x!=y)pre[x]=y;               
    cnt--;
}


int main(){
    cin>>m>>n;
    cnt=m*n;
    for(int i=1;i<=n*m;i++)pre[i]=i;
    int x,y;
    cin>>k;
    for(int i=0;i<k;i++){
        cin>>x>>y;
        join(x,y);
    }
    cout<<cnt+1;
    return 0;
}

Answer 1

第10行判断相等写成赋值了；
join函数中，当x==y时，cnt不能减，应该把cnt--写进if里；
最后cnt不要加1。
这是修改后的代码，试过可以通过。

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

int m, n, k;
int pre[1000005], rankk[1000005] = {0}, cnt;

int find(int x) {
    if (pre[x] == x)return x;
    return pre[x] = find(pre[x]);
}

void join(int x, int y) {
    x = find(x), y = find(y);
    if (x != y) {
        pre[x] = y;
        cnt--;
    }
}

int main() {
    cin >> m >> n;
    cnt = m * n;
    for (int i = 1; i <= n * m; i++)pre[i] = i;
    int x, y;
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> x >> y;
        join(x, y);
    }
    cout << cnt;
    return 0;
}