文章

40

粉丝

512

获赞

18

访问

378.9k

头像
考察一下并查集的概念,签到题
Ang VIP
P1586
发布于2020年3月11日 14:54
阅读数 8.5k

#include<bits/stdc++.h>
using namespace std;

int const MAXN=10001;

int father[MAXN];
int height[MAXN];

void Initial(){
    for(int i=0;i<MAXN;i++){
        father[i]=i;
        height[i]=0;
    }
}

int Find(int x){
    if(x!=father[x]){
        father[x]=Find(father[x]);
    }
    return father[x];
}

void Uinion(int x,int y){
    x=Find(x);
    y=Find(y);
    if(x!=y){
        if(height[x]<height[y]){
            father[x]=y;
        }else if(height[x]>height[y]){
            father[y]=x;
        }else{
            father[y]=x;
            height[x]++;
        }
    }
}


int main(){
    int n,m;
    while(cin>>n>>m){
        Initial();
        while(m--){
            int z,x,y;
            cin>>z>>x>>y;
            if(z==1){
                Uinion(x,y);
            }else{
                if(Find(x)==Find(y)){
                    cout<<"Y"<<endl;
                }else{
...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发