并查集习题题解（牛客）

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

程序自动分析

题意

判定一些约束条件是否能被同时满足，输入 $i, j, e$ ，若 $e = 1$，则该约束条件为 $x_i = x_j$；若 $e = 0$，则该约束条件为 $x_i ≠ x_j$。

注意输入的关系式中的下标最大为 $10^9$，输入的关系式的个数最多 $10^5$ 个。

思路

由于数组长度过大而输入的关系式个数最多为 $10^5$，考虑离线处理，给每一个输入的下标分配一个 id，这样就不会 $MLE$，然后ius离线处理了，将所有的等式存一块，不等式存一块，后面将所有的等式 merge，然后再对所有的不等式进行检查即可。

示例代码

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

void solve() {
    int n;
    cin >> n;

    map<int, int> mp;
 	int cnt = 0;
 	vector<pii> v1, v2;

 	while(n--) {
 		int op, a, b;
 		cin >> a >> b >> op;
 		if(mp.find(a) == mp.end()) mp[a] = ++cnt;
 		if(mp.find(b) == mp.end()) mp[b] = ++cnt;
 		a = mp[a], b = mp[b];

		if(op == 1) v1.push_back({a, b}) 		;
		else v2.push_back({a, b});
 	}

 	DSU uf(cnt);
 	for(auto [a, b] : v1) {
 		uf.merge(a, b);
 	}
 	for(auto [a, b] : v2) {
 		if(uf.same(a, b)) {
 			cout << "NO\n";
 			return;
 		}
 	}
 	cout << "YES\n";
}

银河英雄传说

题意

给两个操作：

1. $M\ i\ j$： 让第 $i$ 号战舰所在的整个战舰队列，作为一个整体(头在前尾在后)接至第 $j$ 号战舰所在的战舰队列的尾部
2. $C\ i\ j$: 询问第 $i$ 号和第 $j$ 号战舰是否在同一个集合，如果是输出两战舰之间包含的战舰数量，否则输出 $-1$

思路

是一个带权并查集问题，权重就是距离，差不多就是一个带权并查集的模板题

示例代码

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, 0);
	}

	int find(int x) {
		if(x == fa[x]) return x;
		int t = fa[x];
		fa[x] = find(fa[x]);
		d[x] += d[t];
		return 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;
			d[ry] = sz[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 t;
    cin >> t;
    DSU uf(N);

    while(t--) {
    	char op;
    	int a, b;
    	cin >> op >> a >> b;
    	if(op == 'M') {
    		uf.merge(b, a);
    	} else if(op == 'C') {
    		int ans = -1;
    		if(uf.same(a, b)) {
    			ans = abs(uf.d[a] - uf.d[b]) - 1;
    		}
    		cout << ans << '\n';
    	}
    }

    return 0;
}

食物链

题意

三种动物 $A, B, C$，构成环形食物链关系。 输入若D=1，则表示 $X$ 和 $Y$ 是同类；若 $D = 2$，则表示 $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)];
	}
};

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

示例代码2

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