概念

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。
它主要解决的是“连通性”问题，或者说“是不是在一个圈子里”的问题。

顾名思义，并查集支持两种操作：

  • 合并（Union）：合并两个元素所属集合（合并对应的树）
  • 查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合

数据结构实现

1
int fa[N]; // 用于记录各个节点的父亲
1
2
3
4
5
6
// 用于找到该节点的根
int findroot(int k)
{
	if(k==fa[k]) return fa[k]; 
	return fa[k] = findroot(fa[k]); // 路径压缩优化
}
1
2
3
4
5
6
7
// 用于连接两个节点
void unite(int i,int j)
{
	int ri=findroot(i);
	int rj=findroot(j);
	fa[ri] = rj;	
}
1
2
3
4
5
6
7
// 判断两个节点是否处于一个集合
bool isunited(int i,int j)
{
	int ri=findroot(i);
	int rj=findroot(j);
	return ri==rj;
}

种类并查集与带权并查集

种类并查集（Species Disjoint Set Union），有时也被称为带权并查集，是普通并查集的升级版。

它不仅记录元素是否属于同一个集合，还记录了集合内部元素之间的关系。

最经典的应用场景是处理“朋友的朋友是朋友，敌人的敌人也是朋友”这类问题。它能回答：“A和B是什么关系？（例如：是同类还是异类/是朋友还是敌人）”。

种类并查集的核心是在并查集的基础上，增加一个数组（通常命名为 d 或 relation），用于存储每个节点到其父节点的关系。

这是一个“相对”关系。我们不知道一个节点的“绝对”身份，但我们知道它和它圈子里其他人的关系。
d[x] 数组的含义是：节点 x 与其父节点 fa[x] 的关系。

关系是可以通过计算来传递的。我们利用模运算来实现

1
2
3
4
// 0 表示朋友关系，1表示敌对关系
(0+0)%2 = 0 // 朋友的朋友是朋友
(0+1)%2 = 1 // 朋友的敌人是敌人
(1+1)%2 = 0 // 敌人的敌人是朋友

find

find 操作：在种类并查集中，路径压缩不仅要更新父节点指针 fa[x]，还必须同时更新关系数组 d[x]。

步骤如下：

  • 找到当前节点x的父节点fa[x]，如果当前节点已经是根x==fa[x]，则直接返回。
  • 否则找到父节点的根rt = findroot(fa[x])，将x到fa[x]的关系d[x]更新为x到rt的关系，通过已知的关系d[x],d[fa[x]]可以推出。
  • 更新父节点fa[x]=rt；
1
2
3
4
5
6
7
8
9
10
int findroot(int x) {
	int f = fa[x];
	if(x!=f) {
		int rt = findroot(f);
		d[x] = (d[x]+d[f]) % 2; // 更新关系数组
		fa[x] = rt; // 更新父节点数组
		return fa[x];
	}
	return f;
}

unite

  • 对元素x与y进行合并时，先找出他们对应的根节点rx,ry。
  • 若两个元素不在同一个集合rx!=ry，则需将其中一个根节点接到另一个根节点上fa[rx]=ry；
  • 进行关系d[rx]的更新，通过已知的d[x](x与rx的关系)，d[y]（y与ry的关系），与x,y之间的关系rel来更新，rx到ry的关系(rx->x + x->y + y->ry)，同时还要注意逆关系，x与rx的关系的逆关系，即rx与x的关系的计算(如上面的例子是d'[x] = (2-d[x])%2)
1
2
3
4
5
6
void unite(int i,int j,int rel) {
    int ri = find_root(i);
    int rj = find_root(j);
    d[ri] =(2- d[i] + rel + d[j]) % 2;
    fa[ri] = rj;
}

例题：食物链 

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
#include <bits/stdc++.h>
#define ll long long
#define fup(i,a,b) for(int i=a;i<=b;i++)
#define fdown(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

const int N = 3*5e4+5;
int n,k;

int fa[N];
int d[N]; // 关系数组；0-同类关系；1-捕食关系；2-天敌关系；

int find_root(int k) {
    int f = fa[k];
    if(k!=f){
        int rt = find_root(f);
        d[k] = (d[k] + d[f])%3; // 更新关系数组
        fa[k] = rt;
        return fa[k];
    }
    return f;
}

void unite(int i,int j,int rel) {
    int ri = find_root(i);
    int rj = find_root(j);
    d[ri] =(3- d[i] + rel + d[j]) % 3;
    fa[ri] = rj;
}

bool isunited(int i,int j) {
    return find_root(i) == find_root(j);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>k;
    int cnt=0;
    // 初始化并查集
    fup(i,1,n) 
    {
        fa[i]=i;
    }
    while(k--) {
        int op,x,y;cin>>op>>x>>y;
        if(x>n || y>n) {
            cnt++; continue;
        }
        int rx=find_root(x);
        int ry=find_root(y);
        if(op==2) {
            if(x==y) {
                cnt++;continue;
            }
            if(rx!=ry) {
                unite(x,y,1);
            }
            else {
                if((d[x] + 3 - d[y]) %3 !=1) {
                    cnt++;continue;
                }
            }
        }
        else if(op==1) {
            if(rx!=ry) {
                unite(x,y,0);
            } else {
                if((d[x] + 3 - d[y]) %3 !=0) {
                    cnt++;continue;
                }
            }
        }

    }
    cout<<cnt;
    return 0;
}