并查集

并查集 - OI Wiki

要求整理出一个比较完整的并查集板子，能够解决 cf 2300 以内的题目。

并查集有：

• 普通并查集
• 带权并查集
• 拓展域并查集
• 可持久化并查集
• 可撤销并查集等。

jiangly 的板子：是以 0 为起点下标。

struct DSU {
    vector<int> f, siz;

    DSU() {}
    DSU(int n) {
        init(n);
    }

    void init(int n) {
        f.resize(n);
        iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }

    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }

    int size(int x) {
        return siz[find(x)];
    }
};

则可以稍加修改，将 {c++}init 函数中的 n 改为 n + 1 即可，以 1 为起点下标。

void init(int n) {
	f.resize(n + 1);
	iota(f.begin(), f.end(), 0);
	siz.assign(n + 1, 1);
}

普通并查集

带路径压缩的查找：

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

普通合并：(一般左边集合是小集合比较好)

void unionset(int x, int y) {
	f[find(x)] == find(y);
}

按照秩合并(启发式合并)：小集合的根指向大集合的根

可持久化并查集、线段树分治 + 并查集中，一般使用只启发式合并的并查集

vector<int> siz(N, 1);
void unionset(int x, int y) {
	x = find(x), y = find(y);
	if(x == y)return;//x=y则代表两个元素是在一个集合，不需要合并
	if(siz[x] > siz[y])swap(x, y);
	f[x] = y;
	siz[y] += siz[x];
}
/* jiangly
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
*/

至于 删除 和 移动 一般做题遇不到，所以不总结。

普通并查集模板：P3367 【模板】并查集

void solve() {
    int n, m;cin >> n >> m;
    DSU dsu(n);
    while (m--) {
        int op, x, y;cin >> op >> x >> y;x--, y--;
        if (op == 1) {
            dsu.merge(x, y);
        } else {
            if (dsu.same(x, y)) {
                cout << "Y\n";
            } else {
                cout << "N\n";
            }
        }
    }
}

拓展域并查集

即根据题目要求将 DSU 的大小开得更大以更方便的满足题目要求。

以拓展域并查集模板为例：

开大小为 $2n$ 的并查集 $(1\sim n),(n+1\sim 2n)$ 分别为朋友域和敌人域

对于 $(x,y)$ 若为朋友，则直接合并

若为敌人 (则 $x$ 和 $y+n$ 是朋友，$y$ 和 $x+n$ 是朋友)，合并 $(x,y+n),(y,x+n)$

void solve() {
    int n, m;cin >> n >> m;
    DSU dsu(2 * n);
    while (m--) {
        char op;int x, y;cin >> op >> x >> y;
        if (op == 'F') {
            dsu.merge(x, y);
        } else {
            dsu.merge(x, y + n);
            dsu.merge(y, x + n);
        }
    }
    set<int>s;
    for (int i = 1;i <= n;i++) {
        s.insert(dsu.find(i));
    }
    cout << s.size() << '\n';
}

例题：P2024 食物链

将动物划分为三部分：同类域，捕食域，天敌域

对于每一次查询 $x,y$ 有：

$x$ 吃 $y$ ：代表 $(x,y+2n),(x+n,y),(x+2n,x+n)$ 是同类，

void solve() {
    int n, m;cin >> n >> m;
    int cnt = 0;
    DSU dsu(3 * n);
    while (m--) {
        int op, x, y;cin >> op >> x >> y;
        if (x > n || y > n) {
            cnt++;continue;
        }
        if (op == 1) {
            if (dsu.same(x, y + n) || dsu.same(x, y + 2 * n)) {
                cnt++;
            } else {
                dsu.merge(x, y);
                dsu.merge(x + n, y + n);
                dsu.merge(x + 2 * n, y + 2 * n);
            }
        } else {
            if (dsu.same(x, y) || dsu.same(x, y + n)) {
                cnt++;
            } else {
                dsu.merge(x, y + 2 * n);
                dsu.merge(x + n, y);
                dsu.merge(x + 2 * n, y + n);
            }
        }
    }
    cout << cnt << '\n';
}

带权并查集

带权并查集模板：P2024 食物链