这是一道关系型并查集的题目，题目意思就不赘述了，毕竟是中文描述。
接下来讲我的解题思路，开一个存储父节点的数组和一个存储与父节点关系的数组（我们姑且称之为这个节点的关系数），然后用数字0代表同类，1代表吃，2代表被吃的关系。用并查集将两个不知道关系的节点相连，并根据输入情况是吃与被吃来为子节点的与父节点的关系赋值。
查找一个节点的祖先节点（也就是根节点）时我们要进行路径压缩把这个节点的父节点修改为根节点，然而这个节点与父亲节点的关系（也就是这个节点的关系数）应该怎么修改呢？其实不难通过验证发现，将这个节点到根节点之间的所有节点的关系数（不包括根节点，但包括初始节点）相加求的和再对3取余就是这个节点与根节点的关系。
合并是当两个节点x，y不属于同一个集合时进行的，也就是说它们的根节点fx，fy不相同，这个时候根据输入的数据我们可以知道x与y的关系，查找x和y的根节点可以让我们知道x与fx，y与fy的关系，那么我们就可以根据这些关系推导得出fx与fy的关系，事实上，这一对关系的关系数是有公式可循的（在代码中会有），现在就可以合并fx与fy了。
另外，题目要求输出假话的总数，在种类为2,3的假话我们很容易就可以判断的了，而种类为1的假话如何判断呢？首先输入的节点x和y必须是拥有共同的根节点我们才可以判断输入的话是否是假话，否则必然是真话。其次因为我们知道x和y分别与他们共同的根节点的关系，所以我们可以推导出x与y的关系，然后我们判断这个关系与输入的关系是否一样就可以了。
接下来是我的解题代码
1 #include <stdio.h> 2 #define N 50001 3 4 int bleg[N]; /*存储父节点*/ 5 int rela[N]; /*存储与父节点的关系，0代表同类，1代表吃，2代表被吃*/ 6 int fake = 0; /*假话的数量*/ 7 int n, k; 8 9 void Init(); /*初始化*/ 10 11 int Find(int x); /*查找根节点*/ 12 13 void Union(int x, int y, int que); /*合并操作*/ 14 15 int main() 16 { 17 int x, y; 18 int que; /*输入的关系*/ 19 scanf("%d %d", &n, &k); 20 Init(); 21 while (k--) 22 { 23 scanf("%d %d %d", &que, &x, &y); 24 if ((que == 2 && x == y) || x > n || y > n) /*满足2或3类别的假话*/ 25 { 26 fake++; 27 continue; 28 } 29 if (Find(x) != Find(y)) /*当且仅当两个节点的根节点不相同时才合并*/ 30 { 31 Union(x, y, que); 32 } 33 else 34 { 35 rela[x] %= 3; 36 rela[y] %= 3; 37 if (que == 1 && rela[x] != rela[y]) /*表示x与y的实际关系与que为1表示的关系冲突*/ 38 { 39 fake++; 40 } 41 else if (que == 2 && !(rela[x] == rela[y] + 1 || (rela[y] == 2 && rela[x] == 0))) 42 { 43 fake++; 44 } 45 } 46 } 47 printf("%d\n", fake); 48 return 0; 49 } 50 51 void Init() /*初始化*/ 52 { 53 int i; 54 for (i=1; i<=n; i++) 55 { 56 bleg[i] = i; 57 rela[i] = 0; 58 } 59 return; 60 } 61 62 int Find(int x) /*用于查找根节点*/ 63 { 64 int y = bleg[x]; 65 while (y != bleg[y]) /*当你的父节点不是根节点，开始修改你与父节点的关系*/ 66 { 67 rela[x] += rela[y]; 68 y = bleg[y]; 69 } 70 bleg[x] = y; /*把父节点修改为根节点*/ 71 return y; 72 } 73 74 void Union(int x, int y, int que) /*合并操作*/ 75 { 76 int fx = Find(x); 77 int fy = Find(y); 78 bleg[fx] = fy; /*先将根节点合并*/ 79 rela[x] %= 3; 80 rela[y] %= 3; 81 /*接下来是分别判断x和y与其根节点的关系*/ 82 if (rela[x] == rela[y]) /*表示x和y分别与其根节点的关系是一样的*/ 83 { 84 rela[fx] = que - 1; /*对应的公式*/ 85 } 86 else if (rela[x] == rela[y] - 1 || (rela[x] == 2 && rela[y] == 0)) /*另外一组关系*/ 87 { 88 rela[fx] = que; /*又是对应的公式*/ 89 } 90 else 91 { 92 rela[fx] = (que + 1) % 3; 93 } 94 return; 95 }