并查集题型总结

本篇对应源码见仓库 solutions/xcpc/algorithm/graph/dsu/。

属性并查集

特点

求一个集合的某个属性的个数，比如在这个集合中有多少个元素是 $x$ 颜色

核心思想

• 对每个集合用 map<int, int> mp 维护这个集合的属性 x 的个数 mp[x]
• vector<map<int, int>> cnt :cnt[root][i] 表示哪个根集合的哪个属性的个数
• 合并集合时，比如将 B 合并到 A，需要遍历 B 的每种属性，将其个数合并到 A 中，然后将 B 的 map 清空

扩展域并查集（种类并查集）

特点

一个点 i 有多个属性，可以用 i, i + n,i + 2 * n 表示 i 的不同属性，如同类、天敌、猎物

核心思想

扩展并查集，比如 uf(3 * n)

模板

来自 食物链

struct DSU {
	int n;
	vector<int> fa, sz;

	// 节点编号从 1 开始
	DSU(int n) : n(n) {
		fa.resize(n + 1);
		iota(all(fa), 0);
		sz.resize(n + 1, 1);
	}

	int find(int x) {
		return x == fa[x] ? x : fa[x] = find(fa[x]);
	}

	void merge(int x, int y) {
		int rx = find(x), ry = find(y);
		if(rx != ry) {
			if(sz[rx] < sz[ry]) swap(rx, ry);
			fa[ry] = rx;
			sz[rx] += sz[ry];
		}
	}

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

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

signed main() {
    IOS;

    int n, k;
    cin >> n >> k;
    DSU uf(3 * n);

    int ans = 0;
    while(k--) {
    	int d, x, y;
    	cin >> d >> x >> y;

    	if(x > n || y > n || x == y && d == 2) {
    		ans++;
    		continue;
    	}
    	if(d == 1) {
    		if(uf.same(x + n, y) || uf.same(x + 2 * n, y)) {
    			ans++;
    			continue;
    		}
    		uf.merge(x, y);
    		uf.merge(x + n, y + n);
    		uf.merge(x + 2 * n, y + 2 * n);
    	} else if(d == 2) {
    		if(uf.same(x + 2 * n, y) || uf.same(x, y)) {
    			ans++;
    			continue;
    		}
    		uf.merge(x + n, y);
    		uf.merge(x + 2 * n, y + n);
    		uf.merge(x, y + 2 * n);
    	}
    }
    cout << ans << '\n';

    return 0;
}

区间合并并查集

特点

实现将区间 $[L, R]$ 内的所有点合并到一个集合，而不需要把区间内每一个点两两 merge

核心思想

通过维护一个“下一个未处理”指针，跳过已经处理过的点，使得每个点在它被“扫过”一次之后就不会再被重复访问，整体复杂度依然是 $O((n+Q),\alpha(n))$。

• find(x) —— 与普通并查集一样
• merge(x, y) —— 与普通并查集一样

模板

struct DSU {
    int n;
    vector<int> fa, sz;
    vector<int> nxt;

    // 节点编号从 1 开始
    DSU(int n) : n(n) {
        fa.resize(n + 1);
        iota(all(fa), 0);
        sz.resize(n + 1, 1);
        nxt.resize(n + 2);
        iota(all(nxt), 1);
    }

    int find(int x) {
        return x == fa[x] ? x : fa[x] = find(fa[x]);
    }

    // 找到编号 ≥ x 的第一个“未跳过”点
    int findNxt(int x) {
        return x == nxt[x] ? x : nxt[x] = findNxt(nxt[x]);
    }

    void merge(int x, int y) {
        int rx = find(x), ry = find(y);
        if(rx != ry) {
            if(sz[rx] < sz[ry]) swap(rx, ry);
            fa[ry] = rx;
            sz[rx] += sz[ry];
        }
    }

    void mergeRange(int l, int r) {
        int x = nxt[l];
        while(x <= r) {
            merge(l, x);
            nxt[x] = r + 1;
            x = findNxt(x);
        }
    }

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

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

signed main() {
    IOS;

    int n;
    cin >> n;
    DSU uf(n);
    vector<int> color(n + 2);

    int q;
    cin >> q;
    while(q--) {
        int op;
        cin >> op;
        if(op == 1) {
            int l, r, c;
            cin >> l >> r >> c;
            uf.mergeRange(l, r);
            color[uf.find(l)] = c;
        } else if(op == 2) {
            int x;
            cin >> x;
            cout << color[uf.find(x)] << '\n';
        }
    }

    return 0;
}

带权并查集

特点

不同节点之间有相对关系，如长度，差值，权重

核心思想

• d[x]: 表示 x 到父节点的距离，通过 find 路径压缩后为 x 到根节点的距离
• find 操作，不仅仅需要通过路径压缩得到根节点，还需要更新 d 数组
• merge 操作，不仅仅考虑集合连通性，还需要更新 d 数组

模板

来自 食物链

struct DSU {
	int n;
	vector<int> fa, sz;
	vector<int> d;

	// 节点编号从 1 开始
	DSU(int n) : n(n) {
		fa.resize(n + 1);
		iota(all(fa), 0);
		sz.resize(n + 1, 1);
		d.resize(n + 1);
	}

	int find(int x) {
		if(x == fa[x]) return x;
		int t = fa[x];
		fa[x] = find(fa[x]);
		d[x] = (d[x] + d[t]) % 3;
		return fa[x];
	}

	void merge(int x, int y, int w) {
		int rx = find(x), ry = find(y);
		if(rx != ry) {
			fa[rx] = ry;
			d[rx] = ((d[y] + w - d[x]) % 3 + 3) % 3;
			sz[ry] += sz[rx];
		}
	}

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

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

signed main() {
    IOS;

    int n, k;
    cin >> n >> k;
    DSU uf(n);

    int ans = 0;
    while(k--) {
    	int d, x, y;
    	cin >> d >> x >> y;

    	if(x > n || y > n || x == y && d == 2) {
    		ans++;
    		continue;
    	}
    	if(d == 1) {
    		if(uf.same(x, y) && (uf.d[x] - uf.d[y] + 3) % 3 != 0) {
    			ans++;
    			continue;
    		}
    		uf.merge(x, y, 0);
    	} else if(d == 2) {
    		if(uf.same(x, y) && (uf.d[x] - uf.d[y] + 3) % 3 != 1) {
    			ans++;
    			continue;
    		}
    		uf.merge(x, y, 1);
    	}
    }
    cout << ans << '\n';

    return 0;
}