2020-2021:teams:no_morning_training:shaco:知识点:数据结构:并查集
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:no_morning_training:shaco:知识点:数据结构:并查集 [2020/07/01 16:56] shaco |
2020-2021:teams:no_morning_training:shaco:知识点:数据结构:并查集 [2020/07/06 09:15] (当前版本) shaco |
||
|---|---|---|---|
| 行 3: | 行 3: | ||
| 并查集应用广泛，用于判断元素是否属于同一个集合以及合并集合。 | 并查集应用广泛，用于判断元素是否属于同一个集合以及合并集合。 | ||
| ==== 复杂度 ==== | ==== 复杂度 ==== | ||
| - | 最坏到 $O(n)$，单独使用路径压缩达到 $O(n+f(1+\log_{2+f/n}n))$，单独使用按秩合并可达到 $O(\log{n})$，两者同时使用可以达到 $O(\alpha (n))$，其中 $\alpha (n)$ 是阿克曼函数的反函数，可以认为非常小（这部分参照网上）。按秩合并即每次将小的集合合并到大的集合中去，可以减少修改次数。 | + | 最坏到 $O(n)$，单独使用路径压缩达到 $O(n+f(1+\log_{2+f/n}n))$，单独使用按秩合并可达到 $O(\log{n})$，两者同时使用可以达到 $O(\alpha (n))$，其中 $\alpha (n)$ 是阿克曼函数的反函数，可以认为非常小。按秩合并即每次将小的集合合并到大的集合中去，可以减少修改次数。 |
| ==== 概念 ==== | ==== 概念 ==== | ||
| 每个集合有一个代表元素，每一个元素通过一个数组记录其所属集合的代表元素。判断两个元素是否属于同一个集合时查询它们的代表元素是否相同，合并集合时将一个集合的代表元素更替为另一个集合的代表元素。 | 每个集合有一个代表元素，每一个元素通过一个数组记录其所属集合的代表元素。判断两个元素是否属于同一个集合时查询它们的代表元素是否相同，合并集合时将一个集合的代表元素更替为另一个集合的代表元素。 | ||
| 行 161: | 行 161: | ||
| [[http://poj.org/problem?id=1182|poj1182]] | [[http://poj.org/problem?id=1182|poj1182]] | ||
| - | 题意：有三种动物，处在一个捕食循环上（$1\to2\to3\to1$），给出若干组捕食或者同类关系，判断假话的数量。假话即是与之前的非假话矛盾的话。 | + | 题意：有三种动物，处在一个捕食循环上（$1\to2\to3\to1$），给出若干组捕食或者同类关系，判断假话的数量。假话即是与之前的非假话矛盾的话或不符合数据范围条件的话（这条不是重点）。 |
| 这一题也是带权值，处理方式和上一题相似，关键在于处理好权值之间的计算关系。 | 这一题也是带权值，处理方式和上一题相似，关键在于处理好权值之间的计算关系。 | ||
| 行 182: | 行 182: | ||
| if(x>n||y>n||(d&&x==y)) return 1; | if(x>n||y>n||(d&&x==y)) return 1; | ||
| int fx=Find(x),fy=Find(y); | int fx=Find(x),fy=Find(y); | ||
| - | //printf("%d %d %d %d %d %d\n",x,y,fx,fy,fa[x][1],fa[y][1]); | ||
| if(fx==fy) | if(fx==fy) | ||
| { | { | ||
2020-2021/teams/no_morning_training/shaco/知识点/数据结构/并查集.1593593805.txt.gz · 最后更改: 2020/07/01 16:56 由 shaco
