并查集

Posted on Edited on In

并查集

并查集：实现为森林，其中每个树表示一个集合。

  • 合并：合并对应的集合（合并树）
  • 查询：查询元素所在集合（查询元素对应根结点）
1
std::vector<int> f;

查询：沿着树向上，直到根结点。

1
2
3
int find(int x){
    return x == f[x] ? x : find(f[x]);
}

路径压缩

直接连至根结点。

1
2
3
int find(int x){
    return x == f[x] ? x : f[x] = find(f[x]);
}

合并

1
2
3
void unite(int x, int y){
    f[find(x)] = find(y);
}

启发式合并

合并时将节点较少，或深度较小的连另一棵。

1
2
3
4
5
6
7
8
9
10
11
12
void unite(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y){
        return;
    }
    if(size[x] < size[y]){
        swap(x, y);
    }
    f[y] = x;
    size[x] += size[y];
}

删除

删除叶子节点，只需将其父亲设为自己。

1
2
3
4
void erase(int x){
    size[find(x)]--;
    find(x) = x;
}

移动

1
2
3
4
5
6
7
8
9
void move(int x, int y){
    int fx = find(x), fy = find(y);
    if(fx == fy){
        return;
    }
    f[x] = fy;
    size[fx]--;
    size[fy]++;
}

应用：Kruskal算法

为了构造一棵最小生成树（森林），每次都选取最小边权的边，若加入此边后产生环则删去，直到加入了\(n-1\)条边。

换句话说，就是维护一堆集合，合并集合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
struct edge{
  int u; int v; int w;
}e[50];

bool cmp(edge a, edge b){
    return a.w < b.w;
}

// n vertex, m edges, construct forest
int kruskal(){
    sort(e, e + m, cmp);
    for (int i = 0; i <= n;i++){
        f[i] = i;
    }
    int ans = 0;
    int cnt = 0;
    for (int i = 0; i < m;i++){
        int u = e[i].u;
        int v = e[i].v;
        int d = e[i].d;
        u = find(u);
        v = find(v);
        if(u != v){
            f[u] = v;
            ans += d;
            cnt++;
        }
    }
    return ans;
}