在所面臨的問題中，我們不僅需要知道兩個元素之間是否存在關(guān)系，還需要記錄其他要素，于是我們需要對原來的并查集進行拓展。

種類并查集

對于一般的并查集，只能表示“朋友的朋友就是朋友這種關(guān)系”，即我們只關(guān)系元素之間的連通性問題。但是對于“敵人的敵人就是朋友”這種關(guān)系則無能為力。種類并查集就是為了解決這種問題，他將一個并查集變成原來的兩倍大小，前一半用來維護朋友關(guān)系，后一半用來描述敵人關(guān)系。

具體步驟詳解

創(chuàng)建

首先我們構(gòu)建原來兩倍大小的并查集
假設(shè)原來大小為4，現(xiàn)在構(gòu)建一個長度為8的并查集，前4個表示朋友關(guān)系，后4個表示敵人關(guān)系。如1和5就是敵人，3和7就是敵人

連接

假設(shè)1 和 2之間是敵人關(guān)系，即2就和5是朋友關(guān)系（敵人的敵人就是朋友，2，5都是1的敵人），1和6就是朋友關(guān)系
再有1和3是敵人關(guān)系，則3和5就是朋友，1和7就是朋友。
如圖：

這樣2和3這樣的敵人的敵人就是朋友關(guān)系即可滿足。

例題

logu P1892 團伙

原題鏈接
顯然，題干直接描述的就是種類并查集，可以有代碼：

#include <iostream>
using namespace std;
const int N = 10e5 + 10;
int tr[N];
void initial(int n) {
	for (int i = 1; i <= 2 * n; i++) tr[i] = i;
}
int find(int x) {
	if (x == tr[x]) return x;
	tr[x] = find(tr[x]);
	return tr[x];
}
void merge(int x, int y) {
	int root_x = find(x), root_y = find(y);
	tr[root_y] = root_x;
}
void solve() {
	int n, m;
	cin >> n >> m;
	initial(n);
	while (m--) {
		char opt;
		int x, y;
		cin >> opt >> x >> y;
		if (opt == 'E') merge(x, y + n), merge(y, x + n);
		if (opt == 'F') merge(x, y);
	}
	int res = 0;
	//在上述代碼中，我們始終是把tr前面的即朋友部分作為根節(jié)點，所以最后有幾棵樹就有多少個圈子
	for (int i = 1; i <= n; i++) res += tr[i] == i ? 1 : 0;
	cout << res << endl;
}
int main() {
	int _ = 1;
	while (_--) solve();
	return 0;
}

logu P1525 關(guān)押罪犯

原題鏈接
假設(shè)發(fā)生最大的事情x，則大于x的兩個人一定在兩個不同的監(jiān)獄中。所以，我們從最大的影響開始，出現(xiàn)的第一矛盾點就是必須發(fā)生的最大影響，有代碼如下：

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 10e5 + 10;
int tr[N], data[N];
struct DA {
	int x, y, val;
};
void initial(int n) {
	for (int i = 1; i <= 2 * n; i++) tr[i] = i;
}
int find(int x) {
	if (tr[x] == x) return x;
	tr[x] = find(tr[x]);
	return tr[x];
}
void merge(int x, int y) {
	int root_x = find(x), root_y = find(y);
	tr[root_y] = root_x;
}
bool cmp(DA &a, DA &b) {
	return a.val > b.val;
}
void solve() {
	int n, m;
	cin >> n >> m;
	DA *da = new DA[m];
	for (int i = 0; i < m; i++) {
		int x, y, val;
		cin >> x >> y >> val;
		da[i].x = x, da[i].y = y, da[i].val = val;
	}
	sort(da, da + m, cmp);
	initial(n);
	int res = 0;
	for (int i = 0; i < m; i++) {
		int x = da[i].x, y = da[i].y, val = da[i].val;
		if (find(x) == find(y)){
			res = val;
			break;
		}
		else {
			merge(x, y + n), merge(y, x + n);
		}
	}
	cout << res << endl;
}
int main() {
	int _ = 1;
	while (_--) solve();
	return 0;
}

帶權(quán)并查集

未完待續(xù)。