一个小问题,玄关

P3367 【模板】并查集

Future_Present @ 2024-08-08 22:16:51

我用pre[]数组维护前驱,find函数用于找前驱,那为什么check函数中不能用pre[a]==pre[b]来判断ab前驱是否一致呢

AC$ $Code
#include<bits/stdc++.h>
using namespace std;
const int N = 200005;
int n,m,pre[N],z,x,y;
int find(int x){
    if(pre[x]==x) return x;
    return pre[x]=find(pre[x]);
}
void Merge(int x,int y){
    int fx=find(x);
    int fy=find(y);
    if(fx!=fy)
        pre[fx]=fy;
    return;
}
bool check(int a,int b){
    if(find(a)==find(b)) return true;
    return false;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        pre[i]=i;
    while(m--){
        cin>>z>>x>>y;
        if(z==1)
            Merge(x,y);
        else if(z==2)
            cout<<(check(x,y)?"Y":"N")<<endl;
    }
    return 0;
}

by mayike @ 2024-08-08 22:21:20

@2023csp

因为祖先可能还没更新到,必须 find

比如1的祖先是2,然后2的祖先是3,如果直接chk:pre[1]==pre[3]肯定错了


by Future_Present @ 2024-08-08 22:29:33

@mayike 感谢,已关


by cgxd @ 2024-08-08 22:51:44

不行,因为a和b的祖先没找到,暂且不能这样下定论,比如a的祖先是c,b的祖先是d,c和d有共同祖先,但是c和d不一样


|