并查集

1
2
3
4
5
6
7
8
9
10
for(int i = 1;i <= n; i++)
    fa[i] = i;
int find(int x) {  //路径压缩
    return (fa[x] == x ? x : fa[x] = find(fa[x]));
}
void merge(int x, int y) {
    int px = find(x), py = get(y);
    if(px == py) return;
    fa[px] =py ;  //将x的父亲改为y
}

连通块大小

1
2
3
4
5
6
void merge(int x, int y) {
    int px = find(x), py = get(y);
    if(px == py) return;
    fa[px] =py ;  //将x的父亲改为y
    siz[py] += siz[px];
}

并查集按秩大小合并（启发式合并）

1
2
3
4
5
6
7
8
vector<int>siz(N, 1);//记录并初始化子集合的大小为1
void unionset( int x , int y){
    int px = find(x), py = find(y);
    if(px == py)return ;
    if(siz[x] > siz[y]) swap(x,y);
    fa[px] = py;
    siz[py] += siz[px];
}