Code 備忘錄►Data Structure

TIOJ::1312 . 家族

http://tioj.infor.org/problems/1312

基礎的 Disjoint sets。

沒什麼特別的，就是要注意可能會有環，遇到環忽略他就好，然後要記得是大連到小。

參考這篇

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#define F(n) Fi(i,n)
#define Fi(i,n) for(int i=0;i<n;i++)
#define N 10001
using namespace std;
int F[N];
int find(int x){
    if(F[x]==x)return x;
    return F[x]=find(F[x]);
}
main(){
    int n,m,a,b,k;
    while(cin>>n>>m){
        F(n)F[i+1]=i+1;
        F(m){
            cin>>a>>b;
            if(find(a)==find(b))continue;
            if(find(a)>find(b))k=a,a=b,b=k;
            F[find(b)]=find(a);
        }
        cin>>k;
        cout<<find(k)<<endl;
    }
}