萌新求带呵呵

sx10086 @ 2017-07-18 09:45:57

#include<bits/stdc++.h>
using namespace std;
int n,m,z,x,y,f[10001];
int finds(int x)
{
if(f[x]!=x)f[x]=finds(f[x]);
return f[x];
}
int main()
{cin>>n>>m;
for(int i=1;i<=n;i++)
{
    f[i]=i;
}
for(int i=1;i<=m;i++)
{
    cin>>z>>x>>y;
    if(z==1){
        int r1=finds(x),r2=finds(y);
        f[r2]=r1;
    }
    if(z==2){
        if(finds(x)!=finds(y))cout<<"N"<<endl;
        else cout<<"Y"<<endl;
    }
}

by 美人为限 @ 2017-07-25 16:27:05

#include<iostream>
#include<vector>
using namespace std;
int fa[10010],n,m;
/*int find(int x){
    while(fa[x]!=x){
        x=fa[x];
    }
    return x;
}*/
//路径压缩 
int find(int x){
    if(fa[x]==x) return x;
    int gen=find(fa[x]);
    fa[x]=gen;
    return gen;
}
void united(int a,int b){
    int gena=find(a);
    int genb=find(b);
    if(gena!=genb){
        fa[gena]=genb;    
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    for(int i=1,z,a,b;i<=m;i++){
        cin>>z>>a>>b;
        if(z==1){
            united(a,b);
        }
        else{
            if(find(a)==find(b)){
                cout<<"Y"<<endl;
            }
            else{
                cout<<"N"<<endl;
            }
        }
    }
    return 0;
}