食物链(Poj 1182 / NOI 2001)
原题描述
题目描述 动物王国中有三类动物 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,表示有 N 个动物,K 句话。 第二行开始每行一句话(按照题目要求,见样例) 输出格式 一行,一个整数,表示假话的总数。 输入输出样例 输入 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 ≤ N ≤ 5 ∗ 10^4 1 ≤ K ≤ 10^5 洛谷链接:https://www.luogu.com.cn/problem/P2024 Poj链接:http://poj.org/problem?id=1182
参考代码一(C++版本)
参考代码一逐步落实并查集的各个需要把握的点,并查集模块化学习路途上的一湾清泉
深化理解
并查集的结构
并查集使用树状结构。每个元素对应这个结点,合并为集合后能够形成对应的树。并查集中最需要的关注的根或者称为老大是谁
并查集的主要模块
1.初始化
让自己做自己的老大
2.合并
像下图一样,从一个组的根向另号一个组的根连边,这样两棵树就变成了一棵树,也就把两个组合并为一个组了。
/
合并的一点好习惯
■对于每棵树,记录这棵树的高度(height)。
■合并时如果两棵树的height不同,那么从height小的向height大的连边。
3.查询
为了查询两个节点是否属于同一组,我们需要沿着树向上走,来查询包含这个元素的树的根是谁。
如果两个节点走到了同一个根,那么就可以知道它们属于同一组。
在下图中,元素2和元素5都走到了元素1,因此它们属于同一组。另一方面,由于元素7走到的是元素6,因此同元素2或元素5属于不同组。
并查集实现中的注意点
为了防止合并以后,对于查找的复杂度会提高,采用了路径压缩的方式
路径压缩
通过路径压缩,可以使得并査集更加高效。
在此之上,不仅仅是所查询的节点,在查询过程中向上经过的所有的节点,都改为直接连到根上。这样再次查询这些节点时,就可以很快知道根是谁了。
并查集的实现
1.前提部分
用数组par表示父亲的编号。par数组里面只存放根结点的信息。par[x] == x 时,x就是所在的树的根
对于每个节点,一旦向上走到了一次根节点,就把这个点到父亲的边改为直接连向根。
int par[MAX_N]; int height[MAX_K];
2.初始化n个元素
for(int i= 1;i <= n ;i++) { par[i] = i; height[i] = 1; }
3.查询树的根
int find(int x) { if(par[x] == x) return x; else return par[x] = find(par[x]); }
4.合并传入参数所属的集合
void unite(int x,int y) { x = find(x); y = find(y); if(x == y) return ; if(height[x] < height[y]) par[x] = y; else { par[y] = x; if(height[x] == height[y]) height[x] ++; } }
5.判断传入参数是否在同一个集合
bool same(int x,int y) { return find(x) == find(y); }
总结:什么是并查集
通过例题的要求和上文的引述,我们可以总结出来,并查集在维护一些散乱的数据元素的时候,可以高效的管理这些数据。并查集也是一种数据结构,是一种用来管理元素分组情况的数据结构。并查集也被称为不相交集数据结构,研究它的人很多,做出主要贡献的是RobertE.Tarjan,这位大师也是深度优先搜索的发明人之一。
并查集主要作用的范围是
- 查询元素a 和 元素 b是否属于同一个组
- 合并元素a和元素b所在的区间