1
int n;
2
vector<int> father;
3
vector<int> sizes;
4

5
void build(){
6
    for(int i=0;i<=n;i++){
7
        father[i]=i;  // 一开始每个元素都指向自己
8
        sizes[i]=1;   // 一开始每个集合都只存在自己，大小为1
9
    }
10
}
11

12
int find(int idx){
13
    stack<int> st;
14
    while(idx!=father[idx]){
15
        st.push(idx);
16
        idx=father[idx];
17
    }
18
    // 实际情况下可以递归简化写法，或者扫两遍
19
    while(!st.empty()){  // 路径压缩/扁平化
20
        father[st.top()]=idx;
21
        st.pop();
22
    }
23
    return idx;
24
}
25

26
int find(int idx){ // 并查集查询操作递归版
27
  if(father[idx]==idx) return idx;
28
  return father[idx]=find(father[idx]);
29
}
30

31
bool isSameSet(int x,int y){
32
    return find(x)==find(y);
33
}
34

35
void unite(int x,int y){
36
    int rx=find(x);
37
    int ry=find(y);
38
    if(rx!=ry){  // 小挂大
39
        if(sizes[rx]>=sizes[ry]){
40
            sizes[rx]+=sizes[ry];
41
            father[ry]=rx;
42
        }
43
        else{
44
            sizes[ry]+=sizes[rx];
45
            father[rx]=ry;
46
        }
47
    }
48
}