POJ-1182 食物链---并查集（附模板）

题目链接：

https://vjudge.net/problem/POJ-1182

题目大意：

中文题，不多说。

思路：

给每个动物创建3个元素，i-A, i-B, i-C

i-x表示i属于种类x，并查集每个组表示组内元素同时发生或者同时不发生

举例说明，

对于x和y属于同一组，合并x和y，合并x+n和 y+n，合并x+2n和y+2n，这里需要判断x和y+n是否是同一组，x和y+2n是否是同一组，如果是的话那就表示出错。

对于x吃y，合并x和y+n，x+n和y+2n，x+2n和y。这里需要判断x和y，x和y+2n是否是同一类

并查集模板：

 1 //初始化n个元素
 2 void init(int n)
 3 {
 4     for(int i = 0; i < n; i++)
 5     {
 6         par[i] = i;
 7         high[i] = 0;
 8     }
 9 }
10 //查询树的根
11 int Find(int x)
12 {
13     return par[x] == x ? x : par[x] = Find(par[x]);//路径压缩
14 }
15 void unite(int x, int y)
16 {
17     x = Find(x);
18     y = Find(y);
19     if(x == y)return;
20     if(high[x] < high[y])par[x] = y;//y的高度高，将x的父节点设置成y
21     else
22     {
23         par[y] = x;
24         if(high[x] == high[y])high[x]++;
25     }
26 }
27 bool same(int x, int y)
28 {
29     return Find(x) == Find(y);
30 }

题解：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<queue>
 7 #include<stack>
 8 #include<map>
 9 #include<sstream>
10 using namespace std;
11 typedef long long ll;
12 const int maxn = 1e6 + 10;
13 const int INF = 1 << 30;
14 int dir[4][2] = {1,0,0,1,-1,0,0,-1};
15 int T, n, m, x;
16 int high[maxn];//树的高度
17 int par[maxn];//父节点
18 //初始化n个元素
19 void init(int n)
20 {
21     for(int i = 0; i < n; i++)
22     {
23         par[i] = i;
24         high[i] = 0;
25     }
26 }
27 //查询树的根
28 int Find(int x)
29 {
30     return par[x] == x ? x : par[x] = Find(par[x]);//路径压缩
31 }
32 void unite(int x, int y)
33 {
34     x = Find(x);
35     y = Find(y);
36     if(x == y)return;
37     if(high[x] < high[y])par[x] = y;//y的高度高，将x的父节点设置成y
38     else
39     {
40         par[y] = x;
41         if(high[x] == high[y])high[x]++;
42     }
43 }
44 bool same(int x, int y)
45 {
46     return Find(x) == Find(y);
47 }
48 
49 int main()
50 {
51     //std::ios::sync_with_stdio(false);
52     cin >> n >> m;
53     init(n * 3);
54     //每个元素用x， x + n, x + 2 * n
55 
56     int c, x, y, ans = 0;
57     while(m--)
58     {
59         scanf("%d%d%d", &c, &x, &y);
60         x--;//把输入变成0到n-1的下标
61         y--;
62         //不正确的编号
63         if(x < 0 || x >= n || y < 0 || y >= n)
64         {
65             ans++;
66             continue;
67         }
68 
69         if(c == 1)//属于同一类
70         {
71             if(same(x, y + n) || same(x, y + 2 * n))ans++;
72             else
73             {
74                 unite(x, y);
75                 unite(x + n, y + n);
76                 unite(x + 2 * n, y + 2 * n);
77             }
78         }
79         else//x吃y
80         {
81             if(same(x, y) || same(x, y + 2 * n))ans++;
82             else
83             {
84                 unite(x, y + n);
85                 unite(x + n, y + 2 * n);
86                 unite(x + 2 * n, y);
87             }
88         }
89         //cout<<ans<<endl;
90     }
91     cout<<ans<<endl;
92     return 0;
93 }