进阶——细赏并查集(1)

简介: 进阶——细赏并查集(1)

食物链(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++版本)


参考代码一逐步落实并查集的各个需要把握的点,并查集模块化学习路途上的一湾清泉


深化理解


并查集的结构


并查集使用树状结构。每个元素对应这个结点,合并为集合后能够形成对应的树。并查集中最需要的关注的根或者称为老大是谁

微信图片_20221017133115.jpg

并查集的主要模块


1.初始化

让自己做自己的老大

微信图片_20221017133200.jpg

2.合并

像下图一样,从一个组的根向另号一个组的根连边,这样两棵树就变成了一棵树,也就把两个组合并为一个组了。

/微信图片_20221017133225.jpg

合并的一点好习惯

■对于每棵树,记录这棵树的高度(height)。

■合并时如果两棵树的height不同,那么从height小的向height大的连边。

微信图片_20221017133308.jpg

3.查询


为了查询两个节点是否属于同一组,我们需要沿着树向上走,来查询包含这个元素的树的根是谁。

如果两个节点走到了同一个根,那么就可以知道它们属于同一组。

在下图中,元素2和元素5都走到了元素1,因此它们属于同一组。另一方面,由于元素7走到的是元素6,因此同元素2或元素5属于不同组。

微信图片_20221017133350.jpg

并查集实现中的注意点


为了防止合并以后,对于查找的复杂度会提高,采用了路径压缩的方式


路径压缩


通过路径压缩,可以使得并査集更加高效。微信图片_20221017133432.jpg

在此之上,不仅仅是所查询的节点,在查询过程中向上经过的所有的节点,都改为直接连到根上。这样再次查询这些节点时,就可以很快知道根是谁了。


并查集的实现


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,这位大师也是深度优先搜索的发明人之一。


并查集主要作用的范围是


  1. 查询元素a 和 元素 b是否属于同一个组
  2. 合并元素a和元素b所在的区间


相关文章
|
6月前
|
算法 C++
c++算法学习笔记 (16) 并查集
c++算法学习笔记 (16) 并查集
|
6月前
|
存储 算法 数据管理
【C++入门到精通】C++入门 ——搜索二叉树(二叉树进阶)
在C++中,本文介绍了搜索二叉树(二叉搜索树,BST)的概念和基本操作,包括搜索、插入和删除。搜索操作从根节点开始,按值大小决定左右查找;插入操作找到合适位置新建节点;删除操作需考虑无子节点、单子节点和双子节点的情况。文中还提供了非递归和递归实现的C++代码示例。此外,讨论了搜索二叉树在K模型和KV模型中的应用以及性能分析,强调了保持树平衡的重要性。
59 0
|
算法
回溯算法总结笔记
回溯算法总结笔记
二分查找进阶版
二分查找进阶版
|
算法 Java 测试技术
二分查找算法简单进阶
这里将对刷题笔记一文末提及的几道推荐二分法进阶题目进行说明介绍。一道简单题加了一定的文字修饰,一道中等题巧用二分查找,以下为刷题笔记一链接,题目链接在文末提供。
153 0
|
算法 索引
数据结构与算法(八) 双指针
数据结构与算法(八) 双指针
66 0
|
存储 算法
【数据结构与算法】并查集
【数据结构与算法】并查集
【数据结构与算法】并查集
|
算法 索引
【数据结构与算法】二分查找算法
【数据结构与算法】二分查找算法
【数据结构与算法】二分查找算法
08数据结构与算法刷题之【并查集】篇
08数据结构与算法刷题之【并查集】篇
08数据结构与算法刷题之【并查集】篇