洛谷 P2024 [NOI2001]食物链

链接：https://www.luogu.org/problemnew/show/P2024
思路：种类并查集，捣鼓捣鼓把题A了，但是没咋懂，列入学习清单，参考了这篇博客和这篇博客
代码：
 1 //#include<bits/stdc++.h>
 2 #include<iostream>
 3 #include<vector>
 4 #include<stack>
 5 #include<string>
 6 #include<cstdio>
 7 #include<algorithm>
 8 #include<queue>
 9 #include<map>
10 #include<set>
11 #include<cmath>
12 #define inf 0x3f3f3f3f
13 using namespace std;
14 typedef long long ll;
15 const int M = int(1e5) * 3 + 5;
16 struct node
17 {
18     int id;
19     int re;//0同类，1吃，2被吃
20 }root[M];
21 void init(int n)
22 {
23     for (int i = 0; i <= n; i++)
24     {
25         root[i].id = i;
26         root[i].re = 0;
27     }
28 }
29 int Find(int x)
30 {
31     /*if (x != root[x].id)
32     {
33         root[x].re = (Find(root[x].re) + root[x].re) % 3;
34         root[x].id = Find(root[x].id);
35     }
36     return root[x].id;*/
37     if (x == root[x].id) return x;
38     int temp = root[x].id;
39     root[x].id = Find(temp);
40     root[x].re = (root[x].re + root[temp].re) % 3;
41     return root[x].id;
42 }
43 //void merge(int x, int y)
44 //{
45 //    x = Find(x);
46 //    y = Find(y);
47 //    if (x != y) root[x].id = y;
48 //}
49 signed main()
50 {
51     int n, k;
52     cin >> n >> k;
53     init(n);
54     int sum = 0;
55     for (int i = 0; i < k; i++)
56     {
57         int op, x, y;
58         cin >> op >> x >> y;
59         if (x > n || y > n)
60         {
61             sum++;
62             continue;
63         }
64         if (op == 2 && x == y)
65         {
66             sum++;
67             continue;
68         }
69         int xx = Find(x);
70         int yy = Find(y);
71         if (xx != yy)
72         {
73             root[yy].id = xx;
74             root[yy].re = (3 - root[y].re + op - 1 + root[x].re) % 3;
75         }
76         else
77         {
78             if (op == 1 && root[x].re != root[y].re)
79             {
80                 sum++;
81                 continue;
82             }
83             if (op == 2 && (3 - root[x].re + root[y].re) % 3 != op - 1)
84             {
85                 sum++;
86                 continue;
87             }
88         }
89     }
90     cout << sum << endl;
91     return 0;
92 }