Acwing算法基础篇(二) 食物链

动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A 吃 B，B 吃 C，C 吃 A。现有 N 个动物，以 1∼N 编号。每个动物都是 A,B,C 中的一种，但是我们并不知道它到底是哪一种。有人用两种说法对这 N 个动物所构成的食物链关系进行描述：第一种说法是 1 X Y，表示 X 和 Y 是同类。第二种说法是 2 X Y，表示 X 吃 Y。此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。当前的话与前面的某些真的话冲突，就是假话；
当前的话中 X 或 Y 比 N 大，就是假话；
当前的话表示 X 吃 X，就是假话。
你的任务是根据给定的 N 和 K 句话，输出假话的总数。输入格式
第一行是两个整数 N 和 K，以一个空格分隔。以下 K 行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中 D 表示说法的种类。若 D=1，则表示 X 和 Y 是同类。若 D=2，则表示 X 吃 Y。输出格式
只有一个整数，表示假话的数目。数据范围
1≤N≤50000,
0≤K≤100000
输入样例：
100 7
1 101 1 
2 1 2
2 2 3 
2 3 3 
1 1 3 
2 3 1 
1 5 5
输出样例：
3

 对示例的解释：
1 101 1：不可能出现超过编号100的动物，因此为假话
2 1 2：1吃2
2 2 3：2吃3
2 3 3：假话
1 1 3：因为整个食物链呈”环形“，所以1被3吃，1与3非同类，这是假话
2 3 1：3吃1，正确
1 5 5：5与5同类
 最终假话有三句，输出3.
 我们基于并查集的思想构建算法。我们将”有关系“的动物放在同一个集合中。举个例子，只要我们知道x与y存在关系，y与z存在关系，那我们是一定能得到x与z的关系的，这基于食物链呈”环形“的前提。
 再进一步，我们渴望探寻每个结点与根结点的关系来得到其对应物种之间的关系。这样的关系又三种，分别是子节点吃根结点，根节点吃子节点，子节点与根节点同类。这样的关系在具体的并查集树中体现成什么？
 联系食物链的”环形”结构，我们选择用距离这一指标来判断它们之间的关系，如下图

 当子节点到根节点的距离取3的余数取值不同时，存在不同的关系，同一个集合里的点可通过这一指标划分为三大类，根节点可看成到自己的距离为0。距离形象点说，假设y为根节点，当出现“x吃y”这类语句时，我们就将x直接连接到y，以此类推，出现"k吃x“时，我们就将直接连接至x。这样子下来x到y距离为1，k到y距离为2，以此类推。所有吃y的，距离都为1，所有吃x的，距离都为2。所有距离为3的，就是y的同类，接下来我们将距离为3的结点看作新的根节点，便又是一次循环，最终的结果就是模三操作。
 需要注意的就是路径压缩问题，初次构建树时每个子节点都存着它到父节点的距离。当我们将一个子节点直接连接至根结点时，它的父节点变成了根结点。我们需要将它到父节点的距离更新为它到根节点的距离。

 上面讲的是如何判断子节点与根结点的关系，而子节点与子节点的关系可以通过”根节点“这个媒介获得。例如x与y同属于一个集合，x与根节点距离为10，y的距离为8，那么有x吃根结点（这样的x我们统称为第一代，根节点为第0代），y则为吃第一代的第二代，同时第二代会被第0代吃。这样通过”第几代代“这样的关系，我们就能很容易的得到x与y的关系。
 再举个例子，x的距离模三为0，y的距离模三为1，这样x就是第0代，y就是第1代，那么y吃x。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 233;
//fa是集合，d是距离
int fa[maxn], d[maxn];
int ff(int x)
{if(fa[x] == x) return x;//递归直到找到根节点int r = ff(fa[x]);//x到根节点的距离等于x到父节点的距离d[x]加上父节点到根结点的距离d[fa[x]]。d[x] += d[fa[x]];//路径压缩操作return fa[x] = r;
}
int main()
{int n,k; cin >> n >> k;//初始化，自己就是一个集合for(int i = 0; i <= n; i++) fa[i] = i;int ans = 0;for(int i = 1; i <= k; i++){//t表示询问的种类int t, a, b;scanf("%d%d%d", &t, &a, &b);//如果大于最大编号，必是假话if(a > n || b > n) {ans ++; continue;}else if(t == 2 && a == b) {ans++; continue;}else{int rel;//x吃yif(t == 2) rel = 1;//x与y同类else rel = 0;int x = ff(a), y = ff(b);//如果它们属于同一个集合if(x == y) {//+3是为了确保一定是正数，第二次模除3是为避免前面的括号数大于2if((((d[a] - d[b]) % 3) + 3) % 3 != rel)ans++;}else{//如果x与y不属于同一集合，需要将他们合并，因为没有矛盾的关系，所以当作是真话fa[x] = y;//原根结点x连接到新根节点y（因为只有x与y同类或x吃y两种可能）//x到y的距离根据关系不同调整，负数不影响d[x] = d[b] - (d[a] - rel);}}}cout<< ans;
}作者：这个显卡不太冷
链接：https://www.acwing.com/solution/content/1357/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。