POJ1988 并查集(3)

1 題意

2 分析

在Find()函數中，如果利用遞歸來更新相關資訊，那麼一定要注意遞歸基的使用，如本題更新node[x].under_number 總是利用 node[old].under_number，而node[old].under_number在上一層遞歸裡會被更新，注意當old==root時的情況。

3

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

const int maxn=3e4+10;
struct Node{
    int all_number;
    int under_number;
    int parent;//s.t.   bottom
}node[maxn];
void Ini(){
    for(int i=1;i<maxn;i++){
        node[i].parent=i;
        node[i].all_number=1;
        node[i].under_number=0;
    }
}
int Find(int x){
    if(node[x].parent==x)   return x;
    else{
        int old=node[x].parent;
        node[x].parent=Find(old);
        node[x].under_number+=node[old].under_number;
        return node[x].parent;
    }
}
void Join(int p1,int p2){
    node[p1].parent=p2;
    node[p1].under_number=node[p2].all_number;
    node[p2].all_number+=node[p1].all_number;
}
int main(){
    int p,n1,n2,p1,p2;
    char com[2];
    while(~scanf("%d",&p)){
        Ini();
        for(int i=1;i<=p;i++){
            scanf("%s",com);
            if(com[0]=='M'){
                scanf("%d%d",&n1,&n2);
                p1=Find(n1);
                p2=Find(n2);
                if(p1!=p2)
                    Join(p1,p2);
            }
            else if(com[0]=='C'){
                scanf("%d",&n1);
                n2=Find(n1);
                cout<<node[n1].under_number<<endl;
            }
        }
    }
}