DSU并查集应用

$DSU$基本应用

240. 食物链
$A,B,C$构成环形

不管是否是同类或者是进食关系, 放到一个并查集中, 只要知道每个点和根节点的关系, 那么两点之间的关系就能确定

如何确定没个点和根节点之间的关系?
并查集维护额外信息, 维护每个点到根节点的距离

因为只有三种动物, 因此可以在$\mathrm{mod}3$条件下判断每个节点和根节点的关系

• $r=0$, 与根节点同类
• $r=1$ 吃根节点的点
• $r=2$ 根节点吃的点
  在路径压缩过程中, 累加到根节点的距离
  
  在该情况下, $d[x]+tmp\equiv d[y](\mathrm{mod}3)$, 说明$x,y$是同类

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 50010;

int n, m;
int fa[N], d[N];

int find(int u) {
   
	if (fa[u] != u) {
   
		int v = find(fa[u]);
		d[u] += d[fa[u]];
		fa[u] = v;
	}
	return fa[u];
}

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= n; ++i) fa[i] = i;

	int res = 0;
	while (m--) {
   
		int op, x, y;
		cin >> op >> x >> y;

		if (x > n || y > n) {
   
			res++;
			continue;
		}
		if (op == 2 && x == y) {
   
			res++;
			continue;
		}

		int px = find(x), py = find(y);
		if (op == 1) {
   
			if (px == py && (d[x] - d[y]) % 3) res++;
			else if (px != py) {
   
				int tmp = d[y] - d[x];
				fa[px] = py;
				d[px] = tmp;
			}
		}
		else {
   
			if (px == py && (d[x] - d[y] - 1) % 3) res++;
			else if (px != py){
   
				int tmp = d[y] - d[x] + 1;
				fa[px] = py;
				d[px] = tmp;
			}
		}
	}

	cout << res << "\n";
	return 0;
}

$DSU$区间染***间覆盖模型

3115. 疯狂的馒头
对于染色操作, 如果倒着枚举, 那么当前馒头染的颜色就是确定的, 因为是最后一次染色操作

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e7 + 10;

int n, m, p, q;
int fa[N], res[N];

int find(int u) {
   
	if (fa[u] != u) fa[u] = find(fa[u]);
	return fa[u];
}

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> m >> p >> q;
	for (int i = 1; i <= n + 1; ++i) fa[i] = i;

	for (int i = m; i; --i) {
   
		int u = (i * p + q) % n + 1;
		int v = (i * q + p) % n + 1;

		int l = min(u, v);
		int r = max(u, v);

		// 找到第一个染色位置的根节点
		int idx = find(l);
		while (idx <= r) {
   
			res[idx] = i;
			fa[idx] = find(idx + 1);
			idx = find(idx);
		}
	}

	for (int i = 1; i <= n; ++i) cout << res[i] << "\n";

	return 0;
}

1242. 修改数组
在该问题中, 并查集的作用是迅速找到下一个可用的值, 对于每个元素$a_i$, 找到下一个可用的值$x$, 因为该元素已经被使用过, 因此将$x$的祖宗节点指向$x+1$, 也就是下一个可用的值是$x+1$

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e7 + 10;

int n;
int fa[N];

int find(int u) {
   
	if (fa[u] != u) fa[u] = find(fa[u]);
	return fa[u];
}

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n;
	for (int i = 1; i < N; ++i) fa[i] = i;

	for (int i = 1; i <= n; ++i) {
   
		int val;
		cin >> val;
		int u = find(val);
		cout << u << " ";
		fa[u] = u + 1;
	}

	return 0;
}

3820. 未出现过的最小正整数
核心思想就是将当前位置合并到下一个位置, 如果下一个位置也出现过, 继续合并到下一个位置, 这样在$find$过程中就会找到第一个未出现的正整数

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 1e5 + 10;

int fa[N];

class Solution {
   
public:
	int find(int u) {
   
		if (fa[u] != u) fa[u] = find(fa[u]);
		return fa[u];
	}

	int findMissMin(vector<int>& nums) {
   
		int n = nums.size();
		for (int i = 1; i <= n + 1; ++i) fa[i] = i;

		for (int val : nums) {
   
			if (val >= 1 && val <= n) {
   
				int u = find(val);
				int v = find(val + 1);
				if (u != v) fa[u] = v;
			}
		}

		return find(1);
	}
};

6100. 奶牛选美

输出每个奶牛被谁击败
每一个集合只有祖宗节点未被淘汰

i = find(i)计算的就是当前区间中第一个未被淘汰的点的位置, 将当前集合的祖宗节点指向下一个位置$i+1$, 因为$i+1$一定未被淘汰, 这样就完成了集合的区间覆盖

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 3e5 + 10;

int n, m;
int l, r, x;
int fa[N], res[N];

int find(int u) {
   
	if (fa[u] != u) fa[u] = find(fa[u]);
	return fa[u];
}

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= n + 1; ++i) fa[i] = i;

	while (m--) {
   
		cin >> l >> r >> x;
		for (int i = l ; i < x; ++i) {
   
			i = find(i);
			if (i < x) {
   
				res[i] = x;
				fa[i] = find(i + 1);
			}
		}
		for (int i = x + 1; i <= r; ++i) {
   
			i = find(i);
			if (i <= r) {
   
				res[i] = x;
				fa[i] = find(i + 1);
			}
		}
	}

	for (int i = 1; i <= n; ++i) cout << res[i] << " ";
	cout << "\n";

	return 0;
}