并查集模板

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

模板一：普通并查集

能解决的问题：

• 判断连通性：
  • find方法
• 计算有多少个连通块
  • 将所有节点的根放入set
• 环检测：
  • 判断是否有环：
    • 如果 $x,y$ 原本就在同一个集合，后续又有连接 $x,y$ 的边，那么就会成环
  • 计算环的个数：
    • 环 = 边 + 1 - 点
• 查询集合大小

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)];
	}
};

模板二：区间合并

能解决的问题：

• 模板一可以解决的问题
• 区间合并问题

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)];
    }
};

模板三：带权并查集

能解决的问题：

• 模板一可以解决的问题
• 节点之间有相对关系

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)];
	}
};