拓展域并查集

拓展并查集的概念

拓展并查集（Union-Find with Extensions）是对标准并查集（Union-Find）的一种扩展，旨在解决更复杂的问题。

拓展域并查集解决了一种多个有相互关系的并查集，放在一起考虑的问题。一般的并查集应用一般就是判断在不在一个集合，拓展域并查集讲的是多个集合，之间有相互关系一般为相互排斥关系，判断是否在一个集合等。

核心思想

为了解决多种关系相互的问题，我们需要更多的空间来维护。

假如我现在有两种关系，友好和敌对，那么我就需要开两倍的空间$p[2 * n]$其中$p[i]$存储的与i是友好关系的,$p[i + n]$ 存储的是与i是敌对关系的。

以此类推:

  • $p[a]$存储与a同类的
  • $p[a+1*n]$存储与a发生第一类关系的
  • $p[a+2*n]$存储与a发生第二类关系的
  • $p[a+3*n]$存储与a发生第三类关系的
  • ….

通过这些关系之间的联系，可以很方便的求解。

例题

食物链

我们还是通过食物链这题来看，这道题有三种关系,同类，食物，天敌。
img
我們分別用$x$代表同类，$x + n$代表食物，$x + n + n $代表天敌。

当我们要判断$x,y$ 是同类这句话是否是假话时，我们要把如果是假话的情况列举出来：

  • x的食物是y
  • x的天敌是y
    这两种情况就是假话，对应代码即为$same(x + n,y) , same(x + n + n,y)$两种任意一种成立即为假话。
    如果是真话的话，就把 这三类都要$merge$一下
  • merge(x,y),
  • merge(x + n,y + n),
  • merge(x + n + n,y + n + n)

因为x和y是同类的话，他们的食物肯定是同类，他们的天敌肯定是同类。

当我们要判断 $x$ 吃 $y$ 也就是说$y$是$x$的食物,$x$是$y$的天敌。
这句话为假时，情况是:

  • x 和 y 同类
  • y 是 x 的天敌

如果这句话是真话，那么我们合并

  • merge(x + n , y)
  • merge(x + n + n, y + n)
  • merge(x , y + n + n)

可以和带权并查集里面的比较一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <iomanip>
#define _fio                      \
	ios_base::sync_with_stdio(0); \
	cin.tie(0);                   \
	cout.tie(0);
#define pb(e) push_back(e)
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define endl '\n'

using namespace std;
using i64 = long long;
using PII = pair<int, int>;
const int INF = 0x3f3f3f3f;

struct DSU
{
	std::vector<int> p, siz;
	DSU() {}
	DSU(int n) { init(n); }
	void init(int n)
	{
		p.resize(n);
		std::iota(p.begin(), p.end(), 0);
		siz.assign(n, 1);
	}
	int find(int x)
	{
		while (x != p[x])
		{
			x = p[x] = p[p[x]];
		}
		return x;
	}
	bool same(int x, int y) { return find(x) == find(y); }
	bool merge(int x, int y)
	{
		int px = find(x);
		int py = find(y);
		if (px == py)
		{
			return false;
		}
		siz[px] += siz[py];
		p[py] = px;
		return true;
	}
	int size(int x) { return siz[find(x)]; }
};
int main()
{
	int n, k, res = 0;
	cin >> n >> k;
	DSU dsu(3 * (n + 1));
	for (int i = 0, d, x, y; i < k; ++i)
	{
		cin >> d >> x >> y;
		if (x > n || y > n)
		{
			res++;
			continue;
		}
		if (d & 1)
		{
			if (dsu.same(x + n, y) || dsu.same(x + n + n, y))
			{
				res++;
			}
			else
			{
				dsu.merge(x, y);
				dsu.merge(x + n, y + n);
				dsu.merge(x + n + n, y + n + n);
			}
		}
		else
		{
			if (dsu.same(x + n + n, y) || dsu.same(x, y))
			{
				res++;
			}
			else
			{
				dsu.merge(x + n, y);
				dsu.merge(x + n + n, y + n);
				dsu.merge(x, y + n + n);
			}
		}
	}
	cout << res << endl;
	return 0;
}

团伙

团伙，这个题只有两种关系，注意的就是，朋友的敌人和自己的敌人不一定是朋友。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <iomanip>
#define _fio                      \
	ios_base::sync_with_stdio(0); \
	cin.tie(0);                   \
	cout.tie(0);
#define pb(e) push_back(e)
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define endl '\n'

using namespace std;
using i64 = long long;
using PII = pair<int, int>;
const int INF = 0x3f3f3f3f;
struct DSU
{
	std::vector<int> p, siz;
	DSU() {}
	DSU(int n) { init(n); }
	void init(int n)
	{
		p.resize(n);
		std::iota(p.begin(), p.end(), 0);
		siz.assign(n, 1);
	}
	int find(int x)
	{
		while (x != p[x])
		{
			x = p[x] = p[p[x]];
		}
		return x;
	}
	bool same(int x, int y) { return find(x) == find(y); }
	bool merge(int x, int y)
	{
		int px = find(x);
		int py = find(y);
		if (px == py)
		{
			return false;
		}
		siz[px] += siz[py];
		p[py] = px;
		return true;
	}
	int size(int x) { return siz[find(x)]; }
};

int main()
{
	int n, m;
	cin >> n >> m;
	DSU dsu(2 * (n + 1));
	while (m--)
	{
		string op;
		int x, y;
		cin >> op >> x >> y;
		if (op == "F")
		{
			dsu.merge(x, y);
			// dsu.merge(x + n, y + n);
		}
		else
		{
			dsu.merge(x + n, y);
			dsu.merge(x, y + n);
		}
	}
	unordered_set<int> st;
	for(int i=1;i<=n;++i)
		st.insert(dsu.find(i));
	cout << st.size() << endl;
	return 0;
}
算法
#algorithm #并查集 #图论 #数据结构
拓展域并查集
http://pikachuxpf.github.io/posts/b6627a60/
作者
Pikachu_fpx
发布于
2024年1月15日
许可协议