并查集(Union-Find)

并查集，故名思意，并，合并；查，查找；集，集合，就是一个可以合并查找的集合嘛，具体的，我们看看百度百科的解释 ``` 并查集，在一些有 N 个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中。其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能用并查集来描述。 并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。常常在使用中以森林来表示。 1）初始化：把每个点所在集合初始化为其自身。通常来说，这个步骤在每次使用该数据结构时只需要执行一次，无论何种实现方式，时间复杂度均为 O(N)。 2）查找：查找元素所在的集合，即根节点。 3）合并：将两个元素所在的集合合并为一个集合。通常来说，合并之前，应先判断两个元素是否属于同一集合，这可用上面的“查找”操作实现。 ``` _**注：上诉解释来自百度百科**_ ~~因为我懒得写~~ ### 理论部分 咳咳，让我们更具体的解释一下 首先，我们先考虑数据类型，最常见的就是整型数组，~~是不是很开心~~，那这个集合应该怎么判断谁是谁呢？ 其实，**这很简单**，~~鲁迅曾说过~~，有图有真相！ 首先，我们要**初始化**，在用并查集的时候，我们一般都是**based 1**，这样方便（题目的）查询，其次，我们把下标为 i 的元素初始化为 i，可能有人已经能看出来了，数组内存的是下标，也就是初始化为**自己指向自己**。  然后，假设我们，要**合并** (3,4)，就将 3 或 4 其中任意一个指向对方  再合并一下 (4,5)。  来，让我们试试**查询**。 想要查询两个数是否在一个集合里，就查询这两个数是不是在**同一个数**的集合里。 ~~废话~~ 查询，也就是递归，一直查询，直到发现自己指向自己。 | 查询 | 内容 | 判断 | 返回 | | :----------: | :----------: | :----------: | :----------: | | find(3) | f[3] == 4 | 4 != 3 | 返回 find(f[3]) | | find(4) | f[4] == 5 | 4 != 5 | 返回 find(f[4]) | | find(5) | f[5] == 5 | 5 == 5 | 返回 5 | ok，理论 ~~存在~~ 结束，实践开始！ ### 代码部份 #### 初始化 ``` for(int i = 1; i <= n; i++) f[i] = i; ``` #### 查询 ``` int find(int x){ if(f[x] == x) return x; else return find(f[x]); } ``` 如果一个函数需要返回，没有保证返回的话，是会警告的，因为 `f[x] == x` 的话已经 `return` 了，所以直接去掉 `else` 就行了。 我们还需要做个**路径优化**，不然每次都要重复一遍，直接 `return f[x] = find(f[x])` ，就相当于  可以少递归很多次。 ``` int find(int x){ if(f[x] == x) return x; return f[x] = find(f[x]); } ``` #### 合并 很简单，先判断两数是否在同一个集合里，如果不在，就将其合并 ``` void merge(int x,int y){ int fx = find(x); int fy = find(y); if(fx != fy) f[fx] = fy; } ```