[TIOJ][並查集] 1312 家族

家族

Time Limit:3000MS  Memory Limit:65536K
Total Submit:385 Accepted:180

Description

義大利黑手黨內有許多家族，家族定義如下：

有n個黨員，依名次為1~n

假如a和b有關係，則說a和b是同一家族的

此時其他與a、b有關係的人都會被視為此家族的人

而每一個家族的人都會選擇當中名次最高者當首領

現在給你其中一個彭哥列家族成員k

要你找出其首領

Input

本題有多組測資

每組測資第一行有兩數，n、m(有幾組關係) (m≤n≤10000)

接下來m行，每行兩數，a和b，代表有關聯的兩人之編號

最後，輸入k，為已知的彭哥列家族成員編號 

Output

對每組測資輸出一數，即為首領編號 

Sample Input

10 6
1 2
3 6
2 7
6 7
4 5
5 8
3

Sample Output

1

Source

TFcis10 留社考。Problem Setter：zenixls2 
---------------------------------------------------------------------------------------------------------
#include<stdio.h>
int p[10005];
int find(int x){
    return x==p[x] ? x : p[x]=find(p[x]);
}
int main(){
    int i,n,m,x,y;
    while(scanf("%d%d",&n,&m)!=EOF){
        for(i=1;i<=n;i++)
            p[i]=i;
        for(i=0;i<m;i++){
            scanf("%d%d",&x,&y);
            x=find(x),y=find(y);
            if(x<y) p[y]=x;
            if(x>y) p[x]=y;
        }
        scanf("%d",&x);
        printf("%d\n",find(x));
    }


}