并查集学习笔记

4.7号做华为实习生笔试，第一题都没完全做出来，用了暴力模拟直接超时，考完后，才知道考察并查集，而且和并查集的经典题目找朋友十分类似，作为一个非科班的，没有系统学习过，只是一直在力扣上刷题，可能刷题少了，没有遇到过并查集的题目(恰巧今天刷每日一题，遇到了并查集)，也是第一次听说并查集，所以写下这篇笔记，一方面记录一下学习流程，另一方面提醒自己基础不扎实
本文根据胡凡老师的算法笔记进行学习的

1.前言

首先从字面上进行理解并查集，并就是合并(Union)，查就是查找(find)，集就是集合(set)，在力扣上的英文标签也是Union find，所以并查集支持两种操作，合并和查找。并查集的实现方式就是数组，利用farther数组表示节点处的父亲，举例说明：father[1] = 1表示1的父亲节点时自己,father[2] = 1表示2的父亲节点时1。对于并查集来说，每个连通的集合都有自己的根节点，所有的根节点都指向自己，如下图所示，就是一个连通的集合，在该集合中，3的父亲节点时1，5的父亲节点是1，7的父亲节点是1，1的父亲节点是4，2的父亲节点是4，4的父亲节点也是4，所有节点的根节点都是4。以上也就是并查集所需要的的基本了解了，下面直接以找朋友这道例题进行详细讲解。

father[3] = 1;//3的父亲节点是1
father[5] = 1;//5的父亲节点是1
father[7] = 1;//7的父亲节点是1
father[1] = 4;//1的父亲节点是4
father[2] = 4;//2的父亲节点是4
father[4] = 4;//4的父亲节点是4

2.例题详解

2.1 题目描述

如果1和2是好朋友，2和3是好朋友，那么1和3也是好朋友，现在给定输入，一共又n个人，n个人的代号分别是1到n，有m组关系（两两之间的关系），问一共可以把这n个人分为几组。（最多有100个人）

输入：
7 5  //7个人，5组关系
1 2  //1和2是好朋友
2 3  //2和3是好朋友
3 1  //3和1是好朋友
1 4  //1和4是好朋友
5 6  //5和6是好朋友
输出：
3 
//解释：由前四组关系可得：1、2、3和4是好朋友，
//由第四组关系可得：5和6是好朋友，由于7和任何人都不是好朋友，所以有三组。

2.2 首先是初始化

也就是先假设每个人都没有好友，每个人都是孤立的，也就是每个人的父亲节点都指向自己。注意：没有代号为0的人，所以从1开始遍历。

int N = 101;
vector<int> father(N, 0);
void init(int n){
    
    for(int i = 1; i <= n; i++){
    
        father[i] = i;
    }
}

初始化后的结果，如下图所示，每个人都是一个集合

2.3 接着合并

也就是将所有人进行分组，每一组都是好朋友。什么是合并，合并就是将有关系的所有人放在一个集合中。放在一个集合中，需要将一个集合的根节点指向另一个集合的根节点（注意区别根节点和父节点，同时一个人也是一个集合，也就是说初始化后的状态有7个集合（0不算），每个集合的节点的父节点和根节点都是自己），所以合并的前提是找到每个集合的根节点，接下来就是根节点的查找过程：
这里也可以用递归实现，就是节点x一直往前遍历，遇到节点的父亲等于节点自己的时候，此时说明x已经为根节点了，跳出循环，返回根节点。

int findRoot(int x){
    
    while(x != father[x]){
    
        x = father[x];//节点x往前遍历
    }
 	return x;
}

扩展：这里可以看到，如果是一条很长的链，查找一次需要从尾遍历到头，查找多次的话，是十分浪费时间的，我们可以在第一次查找x的时候，将所有x之前的节点都之间挂在到根节点，这样的话，等我们再次查找x节点之前的节点的根节点时，就能一步找到根节点了。下面就是路径压缩后的查找根节点算法：

int findRoot(int x){
    
    int a = x;
    while(x != father[x]){
    
        x = father[x];
    }
    //此时x节点存放的是根节点
    //在第一次查找时，将要查找的节点之前所有节点都挂在根节点上
    //步骤：1、保存节点a，防止往前遍历时，变量a被其父亲覆盖
    //2、节点a往根节点进行遍历，保证a之前的节点都能挂在根节点上
    //3、将节点a挂在根节点上
    while(a != father[a]){
    
        int z = a;
        a = father[a];//从节点a处往根节点方向遍历
        father[z] = x;//将z的父亲节点设为x，也就是设为根节点
    }
    return x;
}

实现好查找根节点的函数后，我们就可以实现合并函数了：
查找节点a和节点b的根节点，如果两个根节点不相同，说明他们不在同一集合，将a的根节点的父亲节点设为b的根节点，合并两个集合，如果相同，说明两个节点在一个集合不用操作任何事情。

void Union(int a, int b){
    
    int RoA = findRoot(a);
    int RoB = findRoot(b);
    if(RoA != RoB){
    
        father[RoA] = RoB;
    }
}

2.4 最后就是整体方法的实现了。

数组A里存放的是输入的左列，数组B里面是输入的右列，但是不包括第一行的m和n。
语句1：初始化，将n个人的父节点都设为自己，说明n个人都没有朋友。

语句2：因为输入的左右是好朋友，所以将他们合并到一个集合。
比如之前的7个人，1和2是好朋友，所以Union(1, 2)，1的根节点是1，2的根节点是2，所以将1的父节点设为2。将所有两两关系合并后，得到下面数组：

语句3：本题是最终目的就是找到有几个集合，从语句2所得到的结果可以看出：只要找到根节点的个数，就能找到集合的个数了，巧了，已经实现了找根节点的函数来，接下来定义一个和father数组大小一样的bool类型数组(初始值都是false)isRoot，用来标记哪个节点是根节点。可以看出，1、2、3、4的根节点都是4，所以4的位置标记为true，5和6的根节点为6，所以6的位置标记为true，7的根节点为7，所以7的位置标记为true。
语句4：最后遍历isRoot数组，找出其中为true的个数即可。

int findfriend(int m, int n, vector<int>& A, vector<int>& B){
    
	//语句1
    init(n);
    //语句2
    for(int i = 0; i < m; i++){
    
        Union(A[i], B[i]);
    }
    //语句3
    for(int i = 1; i <= n; i++){
    
        isRoot[findRoot(i)] = true;
    }
    //语句4
    int ans = 0;
    for(int i = 0; i <= n; i++){
    
        ans = ans + isRoot[i];
    }
    return ans;

}

3.总结

其实可以发现并查集的最主要的就是找根节点函数和合并函数，实现这两个函数。最后，本文所写的程序整体代码如下：

#include <iostream>
#include <vector>
using namespace std;
int N = 110 ;
vector<int> father(N, 0);
vector<bool> isRoot(N, false);
//father[2] = 1，索引2是元素，1为元素2的父亲节点
//查找根节点函数
int findRoot(int x){
    
    int a = x;
    while(x != father[x]){
    
        x = father[x];
    }
    //此时x节点存放的是根节点
    //在第一次查找时，将要查找的节点之前所有节点都挂在根节点上
    //步骤：1、保存节点a，防止往前遍历时，变量a被其父亲覆盖
    //2、节点a往根节点进行遍历，保证a之前的节点都能挂在根节点上
    //3、将节点a挂在根节点上
    while(a != father[a]){
    
        int z = a;
        a = father[a];//从节点a处往根节点方向遍历
        father[z] = x;//将z的父亲节点设为x，也就是设为根节点
    }
    return x;
}
//合并函数
void Union(int a, int b){
    
    int RoA = findRoot(a);
    int RoB = findRoot(b);
    if(RoA != RoB){
    
        father[RoA] = RoB;
    }
}
void init(int n){
    
    N = n;
    for(int i = 1; i <= n; i++){
    
        father[i] = i;
        isRoot[i] = false;
    }
}
int findfriend(int m, int n, vector<int>& A, vector<int>& B){
    
    init(n);
    for(int i = 0; i < m; i++){
    
        Union(A[i], B[i]);
    }
    for(int i = 1; i <= n; i++){
    
        isRoot[findRoot(i)] = true;
    }
    int ans = 0;
    for(int i = 0; i <= n; i++){
    
        ans = ans + isRoot[i];
    }
    return ans;

}
int main(void){
    
    /*int n, m, a, b;
    cin>>n>>m;
    vector<int> A;
    vector<int> B;
    for(int i = 0; i < m; i++){
        cin>>a>>b;
        A.push_back(a);
        B.push_back(b);
    }*/
    int m = 5;
    int n = 7;
    vector<int> A = {
    1, 2, 3, 1, 5};
    vector<int> B = {
    2, 3, 1, 4, 6};
    cout<<findfriend(m, n , A, B)<<endl;
    return 0;
}

4.华为4.7笔试题解

可以根据上述解法解华为4.7号的机试第一题（两题基本相同）
题目来自于牛客网
题目描述：幼儿园老师安排小朋友做游戏，现在需要安排给N个小朋友分组，老师让每个同学写一个名字，代表这个小朋友想和谁分到一组。请问老师在满足所有小朋友意愿的情况下，最多可以将班级分为几组？
输入描述：

第一行输入N，0 < N <= 10000
接下来是N行代表小朋友希望和谁分到一组，如"john jack"，代表john希望和jack分为一组，两个名字之间以空格分割，名字本身不存在空格。

输出描述：

分组的最多数量

示例1
输入：

6
jack tom
alice john
jessica leonie
tom alice
john jack
leonie jessica

输出;

2

代码：

#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;
map<string, string> father;
map<string,bool> flag;
void init(vector<string>& vs1){
    

    for(int i = 0; i < vs1.size(); i++){
    
        father[vs1[i]] = vs1[i];
        flag[vs1[i]] = false;
    }
}
string findRoot(string& s){
    
    string a = s;
    while(s != father[s]){
    
        s = father[s];
    }
    while(a != father[a]){
    
        string z = a;
        a = father[a];
        father[z] = s;
    }
    return s;
}
void Union(string& s1, string& s2){
    
    string s1Root = findRoot(s1);
    string s2Root = findRoot(s2);
    if(s1Root != s2Root){
    
        father[s1Root] = s2Root;
    }
}
int myfun(vector<string>& vs1, vector<string>& vs2){
    
    int cnt = 0;
    init(vs1);
    for(int i = 0; i < vs1.size(); i++){
    
        Union(vs1[i],vs2[i]);
    }
    for(auto n: father){
    
        flag[findRoot(n.second)] = true;
    }
    for(auto n : flag){
    
        if(n.second == true){
    
            cnt++;
        }
    }
    return cnt;
}

int main() {
    
    /*int n;
    cin>>n;
    string s1;
    string s2;
    vector<string> vs1;
    vector<string> vs2;
    for(int i = 0; i < n; i++){
        cin>>s1>>s2;
        vs1.push_back(s1);
        vs2.push_back(s2);
    }*/
    vector<string> vs1 = {
    "jack","alice","jessia","tom","john","leonie","l","y","f"};
    vector<string> vs2 = {
    "tom","john","leonie","alice","jack","jessia","y","f","l"};
    cout<<myfun(vs1,vs2)<<endl;
    return 0;
}