并查集模板

1
2
3
4
5
int find(int x)
{
		if(q[x] != x) q[x] = find(q[x]);
		return q[x];
}

路径压缩思想, 每次执行一次find x直接连接到x的祖宗;

附带额外信息的并查集应用

240. 食物链

题目要求我们分为三类 ABC循环吃.

我们可以用一个路径距离来表示ABC之间的关系, 若A的路径大于B则表示 A 能够吃 B

分别用不同的路径对3求余来表示表示每个点是什么种类

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
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 500010;

// p表示节点的父节点. d表示到根节点的距离
int p[N], d[N], n, m;
int ret;

int find(int x)
{
    if(x != p[x])
    {
      	// 先找到x的祖宗, 然后当前节点加上祖宗到根节点的距离, 最后连接到根节点
        int t = find(p[x]);
        d[x] += d[p[x]];
        p[x] = t;
    }
    return p[x];
}

int main()
{
    cin >> n >> m;
  
  	// 初始化并查集
    for(int i = 0 ;i <= n; i++) p[i] = i;
  
    while(m--)
    {
        int t,x,y;
        cin >> t >> x >> y;
      
      	// 判断x和y是否符合题意
        if(x > n || y > n) ret++;
        else
        {
            int px = find(x), py = find(y);
            if(t == 1)
            {
              	// 如果x和y的祖宗相同, 则计算x和y是否是同一类
                if(px == py && (d[x] - d[y]) % 3) ret++;
                else if(px != py) // x和y不是同一类的情况下将xy合并
                {
                  	// 合并xy为同一类
                    p[px] = py;
                  	// 设置x祖宗的距离, 表示两点之间的差值, 当执行一次findx之后, x将会加上他们之间的差值,此时 dx = dy
                    d[px] = d[y] - d[x];
                }
            }
            else
            {
              	// 如果x和y的祖宗相同, 计算x是否能够吃掉y
              	// 求余计算公式 x % 3 - y % 3 = 1
              	// 化简后得 ( x - y ) % 3 = 0
                if(px == py && (d[x] - d[y] - 1) % 3) ret++;
                else if(px != py)
                {
                    p[px] = py;
                  	// x 祖宗的根路径+1, 同理将他们的差值加到x的祖宗节点
                    d[px] = d[y] - d[x] + 1;
                }
            }
        }
    }

    cout << ret;
    return 0;
}