並查集

並查集是一種樹狀結構，他支援兩件事

查詢所隸屬集合
合併兩個集合

我們把集合轉化成樹，一顆樹代表一個集合，樹根代表集合的老大，查詢隸屬集合就回傳樹根是誰（一個樹餔可能有兩顆樹根吧），合併的時侯，就把一顆樹的樹根只到另一顆，以下為詳細的描述。

初始

一開始的時候，每個點自成一個集合，所以把樹根都設為自己。

查詢

查詢的時候，要查到樹根為自己的點，為止否則的話就要繼續查。

int Find(int x)
{
    if (x == p[x])
        return x;
    return find(p[x]);
}

狀態壓縮：在合併之後原本被指向的樹根就沒用了，我們可以一邊做查詢時，一邊做更新。

int Find(int x)
{
    if (x == p[x])
        return x;
    return p[x] = find(p[x]);
}

合併

找出兩個點的樹根，將一個樹根合併指到另一個樹根。

void Union(int a, int b)
{
    a = Find(a);
    b = Find(b);
    if (a == b)
        return;
    p[a] = b;
}

啟發式合併：建立一個 $h[i]$ 代表樹的高度，亦是元素最大遞迴次數， $h[i]$ 一開始為 $1$ 。再來，我們每次都讓高度小的高度大的合併，如果遇到高度一樣的，就讓合併別人的樹高度加 $1$ 。如果要把高度變為 $x$ ，則至少需要 $2^x$ 個點，由此推出 N 個點所形成最高之高度為 $\log(N)$ 。

void Union(int a, int b)
{
    a = Find(a);
    b = Find(b);
    if (a == b)
        return;
    if (rank[a] < rank[b])
        p[a] = b;
    else if (rank[a] > rank[b])
        p[b] = a;
    else
    {
        p[a] = b;
        rank[a]++;
    }
}

也可以維護並查集的個數，個數大的合併個數小的並查集。

void Union(int a, int b)
{
    a = Find(a);
    b = Find(b);
    if (a == b)
        return;
    if (sz[a] < sz[b])
        swap(a, b);
    sz[a] += sz[b];
    p[b] = a;
}

完整程式碼

int p[N], rank[N];
void init()
{
    for (int i = 0; i < N; i++)
    {
        p[i] = i;
        rnak[i] = 1;
    }
}
int Find(int x)
{
    if (x == p[x])
        return x;
    return p[x] = find(p[x]);
}
void Union(int a, int b)
{
    a = Find(a);
    b = Find(b);
    if (a == b)
        return;
    if (rank[a] < rank[b])
        p[a] = b;
    else if (rank[a] > rank[b])
        p[b] = a;
    else
    {
        p[a] = b;
        rank[a]++;
    }
}

帶權並查集

在並查集上增加數值，數值會在查詢的時候更新，讓並查集能解決更多問題。

更新原則：我到根節點的距離=我到父節點的距離+父節點到根節點的距離。

int find(int u) // p[u]: 父節點, root: 根節點
{
    if (u != p[u])
        return p[u];
    int f = p[u];
    int root = find(p[u]);
    v[u] += v[p[u]];
    return p[u] = root;
}

UVa 01329 - Corporative Network

給定 $N$ 個節點和兩種操作，一開始每個點都沒有父節點。 - E x: 輸出 x 到根節點的距離。 - I x y: 將 x 的父節點設為 y，距離為 $|x-y|\ \mod 1000$ 。

帶刪除並查集

刪除操作是指將特定點 $u$ 從當前集合移除，自己獨立一個集合或是加入新的集合，實作步驟如下：

開一個陣列維護每個點的編號。
- 查詢 $x$ : Find(id[x])。
- 合併 $x,y$ : Union(id[x],id[y])。
將從當前集合移除
- 扣除 $u$ 在原本集合的貢獻。
- 為 $id[u]$ 產生新的編號。
- 保留舊編號，否則會影響 $u$ 原本的子節點。

UVa 11987 - Almost Union-Find

給定 $N$ 個點和 $M$ 筆操作，一開始每個點都是自己一個集合，操作有三種： - 1 p q: 將 $p,q$ 所在的集合合併。 - 2 p q: 將 $p$ 和 $q$ 所在的集合合併。 - 3 p: 詢問 $p$ 所在的集合元素個數和總和。

參考程式碼

#include <bits/stdc++.h>
using namespace std;
const int MXV = 200000 + 5;

int p[MXV], sum[MXV], sz[MXV];
int tot = -1, id[MXV];
struct DisjointSet
{
    void init(int n = MXV - 1)
    {
        for (int i = 0; i <= n; i++)
        {
            sz[i] = 1;
            p[i] = i;
            sum[i] = i;
            id[i] = i;
        }
        tot = n;
    }
    int find(int u) { return u == p[u] ? u : find(p[u]); }
    void Union(int x, int y)
    {
        int fx = find(id[x]), fy = find(id[y]);
        if (fx == fy)
            return;
        sz[fy] += sz[fx];
        sum[fy] += sum[fx];
        p[fx] = fy;
    }
};

int main()
{
    int n, m;
    DisjointSet djs;
    while (cin >> n >> m)
    {
        int x, y, z;
        djs.init(n);
        for (int i = 0; i < m; ++i)
        {
            cin >> x;
            if (x == 3)
            {
                cin >> y;
                int fy = djs.find(id[y]);
                cout << sz[fy] << ' ' << sum[fy] << '\n';
                continue;
            }
            cin >> y >> z;
            int fy = djs.find(id[y]), fz = djs.find(id[z]);
            if (fy == fz)
                continue;
            if (x == 2)
            {
                // remove from old set
                sz[fy] -= 1;
                sum[fy] -= y;
                // create new set
                id[y] = ++tot;
                p[id[y]] = id[y];
                sz[id[y]] = 1;
                sum[id[y]] = y;
            }
            djs.Union(y, z);
        }
    }
}

最近更新: 2024-01-01
本文貢獻者: allem40306,

並查集

初始

查詢

合併

完整程式碼

相關題目

帶權並查集

帶刪除並查集