神机百炼2.33-并查集

• • 食用指南：
  • 题目描述：
  • 题目分析：
  • 算法原理：
  • • 模板算法：
    • 并查集：
    • • 1. 辅助结构：
      • 2. 查询操作：
      • 3. 合并操作：
      • 4. 统计区间内点数：
  • 代码实现：
  • 代码误区：
  • • 1. 查询时如何让一条链表结构转化为中心结构？
    • 2. 最终的集合结构：
    • 3. find()查找的功能：
    • 4. 为什么最终判断是否共处一个集合还需要find?
    • 5. 为什么求一个点所属集合中点的数目还需find()？
    • 6. 为什么求一个集合中点的数目需要额外借助count[N]数组？
    • 7.需不需要将fa[N]和count[N]的初始化单独写作函数？
• 本篇感想：

对该算法程序编写以及踩坑点很熟悉的同学可以直接跳转到代码模板查看完整代码
只有基础算法的题目会有关于该算法的原理，实现步骤，代码注意点，代码模板，代码误区的讲解
非基础算法的题目侧重题目分析，代码实现，以及必要的代码理解误区

• 给定一个包含 n 个点（编号为 1∼n）的无向图，初始时图中没有边。
  现在要进行 m 个操作，操作共有三种：
  C a b，在点 a 和点 b 之间连一条边，a 和 b 可能相等；
  Q1 a b，询问点 a 和点 b 是否在同一个连通块中，a 和 b 可能相等；
  Q2 a，询问点 a 所在连通块中点的数量；

  输入格式
  第一行输入整数 n 和 m。
  接下来 m 行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。

  输出格式
  对于每个询问指令 Q1 a b，如果 a 和 b 在同一个连通块中，则输出 Yes，否则输出 No。
  对于每个询问指令 Q2 a，输出一个整数表示点 a 所在连通块中点的数量
  每个结果占一行。

  数据范围
  1≤n,m≤10⁵
  输入样例：
  5 5
  C 1 2
  Q1 1 2
  Q2 1
  C 2 5
  Q2 5
  输出样例：
  Yes
  2
  3

• 题目来源：https://www.acwing.com/problem/content/838/

• 整个题目就涉及集合的两个操作：合并 & 查询
• 并查集经典题目
• 下面介绍并查集，一种专在O(1)内判断集合关系的数据结构

• 传送门：无，本次就是并查集的最基本讲解

• 使用一个数组fa[]记录当前节点和哪个节点同属一个集合
• 举例：
  例1：fa[6] = {0,0,2,0,0,2};
  
  例2：fa[6] = {0,0,2,1,3,2};
  
  上述两种方式都将6个点分为了2个集合
  法一围绕一个中心
  法二连接到了集合中即可，没必要同一点
• 作为集合围绕中心的点x，其fa[x] == x;
  不是集合中心的点y，其fa[y] != y;

• 并查集虽然叫并查集，并在查前，但是其实查找才是核心，因为查找不只找到集合中心
• 递归查找：
  1. 当该点是集合中心时，直接返回自己
  2. 若该点不是集合中心，则就像图二中的列表一样，不断迭代fa[fa[fa[fa[x]]]]，
     直到迭代到集合中心时，将迭代沿途所有非集合中心的fa[]修改为集合中心

int find(int x){
	if (fa[x] == x) return x;
	fa[x] = find(fa[x]);
	return fa[x];
}

• 通过查询，图二的一条链表结构转化为图一的中心结构，
  可以说，图二经过最多 链表条数 次查询后就是图一结构

• 将两个集合合并，其实只要将两个区间的中心点连接即可
• 由于合并两个集合本身涉及两次查询，
  所以就算合并时集合不为中心结构，
  查询时一条链表就会被修正为中心结构

void uni(int x, int y){
    int fax = find(x);
    int fay = find(y);
     //由于涉及到了集合内点数的合并，所以千万不能出现同一集合和自己合并导致点数增加的情况
    if (fax < fay){
        fa[fay] = fax;
        count[fax] += count[fay];
    }
    else if (fax > fay) {
        fa[fax] = fay;
        count[fay] += count[fax];
    }
}

• 必须借助count[N]数组辅助记录，否则必超时，分析在下面
• 初始化：
  初始每个节点都是独立一个区间，count[i] = 1;
• 集合合并：
  在a所属集合和b所属集合合并时，必然是一者归附于另一者
  当a归附于b时，count[b] += count[find(a)];
  之后也不必管cout[a]了，因为所有于a连接的点都会find()到b，之后输出的是count[b]，a再也不会被当中心点看待

#include 
using namespace std;
const int N = 100010;
int n;
int fa[N];
int count[N];
void init(){
	for(int i=1; i<=n; i++)  fa[i] = i,count[i] = 1;
}
int find (int x){
    if (fa[x] == x) return x;
    fa[x] = find(fa[x]);
    return fa[x];
}
void uni(int x, int y){
    int fax = find(x);
    int fay = find(y);
    //注意点1：切记同一集合不可和自身进行点数相加
    if (fax < fay){
        fa[fay] = fax;
        count[fax] += count[fay];
    }
    else if (fax > fay) {
        fa[fax] = fay;
        count[fay] += count[fax];
    }
}

int main(){
    int m = 0;
    cin >>n >>m;
    init();
    while(m--){
        string s;
        cin >>s;
        if (s =="C"){
            int x = 0, y = 0;
            cin >>x >>y;
            uni(x, y);
        }else if (s == "Q1"){
            int x=0, y=0;
            cin >>x >>y;
            if (find(x) == find(y)) cout<< "Yes" <
            int x = 0;
            cin >>x;
            cout < 
代码误区： 
1. 查询时如何让一条链表结构转化为中心结构？ 
当查询到集合中心时，一层层褪去fa[fa[fa[fa[x]]]]的时候，为每一层fa[]直接指向了集合中心
 
2. 最终的集合结构： 
最多经过 节点数 -1 次查询操作后
仍可能有集合不连通
但所有连通的集合内部，都是直接连接到一个中心点
 
3. find()查找的功能： 
直接功能就是获取了 节点所属集合的集合中心
间接功能更重要，将所有原本未直接连接到集合中心的节点，现在直接连接到一起
不要忘记，合并本身也用了查找
 
4. 为什么最终判断是否共处一个集合还需要find? 
 
假设两个集合各围绕中心连接着两条链表
 
 
 
现在将节点a和节点h进行合并操作，假设合并到h点
 - 可以看到fa[e] == d， fa[j] == h 但是他们本身属于1个集合
 所以判断x y是否共处一个集合时，还需要进行查询操作
 
 
find(e) & find(j)之后：
 
 
find(e) == h == find(j)
 
 
5. 为什么求一个点所属集合中点的数目还需find()？ 
每个集合中点数是存储在count[集合中心]的，不find()找不到集合中心
和判断是否共处一个集合不同，此处不是因为部分链表结构未转化为中心结构
 
6. 为什么求一个集合中点的数目需要额外借助count[N]数组？ 
暴力求解：
 
int count(int x){
    int fax = find(x);
    int num = 0;
    for(int i=1; i<=n; i++){
        if (find(i) == fax)
            num++;
    }
    return num;
}
 
若每次询问都将N个节点的fa[]遍历一遍，共m次询问
 mn 最大 1010,远超时
但是count[find(x)]仅仅O(1)
 
7.需不需要将fa[N]和count[N]的初始化单独写作函数？ 
我的建议是需要
 因为熟练度上去后，反而find() uni() count[]不出错，出错出在了未初始化
 另一个易错点就是count[N]中的同一集合点数自增
memset()是按照1个字节赋值的
 所以不能用来为4字节的count[]初始化为1，倒是可以用来为fa[]初始化为0
 
本篇感想： 
并查集只有两个操作，且关键在 查，容易错在 初始化 & count[]同一集合自增
看完本篇博客，恭喜已登 《练气境-后期》
 36篇左右进入图论，还不熟悉dfs bfs的小伙伴看这里：【算法设计】用C++类和队列实现图搜索的广度优先遍历算法
 
 距离登仙境不远了，加油