vj家族（最基本的并查集）

2009-05-12 10:45

#include<iostream>
using namespace std;

int father[5010],rank[5010];
int n,m,p;

void Init();
void Judge(int x,int y);
void Union(int x,int y);

int main(void){
    int i,a,b;
   
    cin>>n>>m>>p;
    Init();
    for(i=0;i<m;i++){
        cin>>a>>b;
        Union(a,b);
    }
   
    for(i=0;i<p;i++){
        cin>>a>>b;
        Judge(a,b);
    }
   
    system("pause");
    return 0;
}

void Init(){
     for(int i=1;i<=n;i++){
         rank[i] = 0;
         father[i] = i;
     }
}
    
void Judge(int x,int y){
     while(x!=father[x]) x = father[x];
     while(y!=father[y]) y = father[y];
    
     if(x==y) cout<<"Yes"<<endl;
     else cout<<"No"<<endl;
}
    
void Union(int x,int y){
     while(x!=father[x]) x = father[x];
     while(y!=father[y]) y = father[y];
    
     if(rank[x]>rank[y]) father[y] = x;
     else if(rank[y]>rank[x]) father[x] = y;
     else{
         rank[x]++;
         father[y] = x;
     }
}