来个nb侠解释一下

P3367 【模板】并查集

CodeEmperor @ 2024-08-13 10:28:21

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+10;
int n,m,p,fx[N];

int find(int i){
    if(fx[i] == i ) return fx[i];
    return fx[i]=find(fx[i]);//这里原本是return find(fx[i]) 结果会有3个样例超时但是后面改成 return fx[i]=find(fx[i])就样例全ac了
}
void insert(int x,int y)
{
    int f1 = find(x),f2 = find(y);
    if(f1 != f2){
        fx[f1]  = f2;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        fx[i] = i;
    }
    while(m--){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        if(x==1){
            insert(y,z);
        }else{
            int f1 = find(y),f2 = find(z);
            if(f1 == f2){
                cout<<"Y"<<endl;
            }else{
                cout<<"N"<<endl;
            }

        }

    }        
    return 0;

}

by Po7ed @ 2024-08-13 10:29:16

@CodeEmperor 路径压缩,并查集基本优化之一


by CodeEmperor @ 2024-08-13 10:34:08

@Po7ed 谢谢


|