[Algo][July][Notes+Homework]并查集的应用

并查集顾名思义就是有“合并集合”和“查找集合”两种操作的关于数据结构的一种算法。

假设n个节点,初始时点与点之间没有连接
• 给出一系列的连接操作
• 一次连接操作不产生环,则接受,否则被抛弃

算法课上老师出的题目太抽象了。先引入一个简单具体的问题：

reference website:

//概念描述：

https://segmentfault.com/a/1190000004023326

//例题描述

https://segmentfault.com/a/1190000000752006

假如已知有n个人和m对好友关系（存于数字r）。如果两个人是直接或间接的好友（好友的好友的好友...），则认为他们属于同一个朋友圈，请写程序求出这n个人里一共有多少个朋友圈。
假如：n = 5 ， m = 3 ， r = {{1 , 2} , {2 , 3} , {4 , 5}}，表示有5个人，1和2是好友，2和3是好友，4和5是好友，则1、2、3属于一个朋友圈，4、5属于另一个朋友圈，结果为2个朋友圈。

从这道题的角度出发，也就是有5个节点，3条边（1条边表示两个节点之间有关系）。要把互相能到达的节点合并成一个集合。最后判断父节点的个数，就是有多少个朋友圈。

1. 如何表示节点：

机构体表示法：

#define MAX 10000
struct Node
{
    int data;    //数据
    int rank;    //层级
    int father; //父节点
 }node[MAX];

数组表示法：

int father[max]; //集合index的类别
int rank[max];//集合index的层次，通常初始化为0,C++里面用rank会和某个关键字冲突，所以C++里面要换一个数组名
int data[max];//集合index的数据类型

2.初始化节点：

void init(int i){
    father[i] = i; //初始化，每个人的父节点都是自己
    rank[i] = 0; //每层都是0
}

3.合并节点：

 1 void unionSet(int a, int b){
 2     a = find(a); //找a的父节点,这时候的变量a已经是自己的父节点了
 3     b = find(b); //找b的父节点，这时候的变量b也是自己的父节点，下面代码注意区分
 4     if(a == b){   //a和b的父节点相同，属于同一集合，不需要合并
 5         return;
 6     }
 7     if(rank[a]>rank[b]){ //a的层数比b的层数大
 8         father[b] = a;  //把父节点b指向a，b的父节点变成了a
 9     }
10     else {
11         father[a] = b;  //a的的父节点变成b
12         if(rank[a]==rank[b]){
13             rank[b]++;
14         }
15     } 
16 }

4.寻找父节点：

1 int find(int x){ //寻找父节点
2     if(x == father[x]){  //如果这个节点是父节点则返回
3         return x;
4     }
5     else{
6         return find(father[x]);  //如果这个节点不是父节点，那么再往上寻找这个节点的father的father
7     }
8 }

在这个过程中可以进行路径压缩：

1 int findSet(int d){
2     if(d != father[d]){
3         father[d] = findSet(father[d]); //使这条路径上的所有子节点直接指向父节点
4     }
5     return father[d];
6 }

5. 问题答案：

 1 #include<cstdio>  
 2 #include<iostream>
 3 using namespace std;
 4 #define MAX 6
 5 int father[MAX];
 6 int ran[MAX];
 7 void init(){
 8     for(int i = 1;i < MAX;i++){
 9         father[i]=i;
10         ran[i] = 0;
11     }
12 }
13 
14 int findSet(int d){
15     if(d != father[d]){
16         father[d] = findSet(father[d]);
17     }
18     return father[d];
19 }
20 
21 void unionSet(int a, int b){
22     a = findSet(a); 
23     b = findSet(b); 
24 
25     if(a == b){   //我自己在写的时候，这其中犯了一个致命的错误，if里面的恒等条件写成了赋值，导致合并集合失败。
26         return;
27     }
28     if(ran[a]>ran[b]){ 
29         father[b] = a;  
30     }
31     else {
32         father[a] = b;  //a的的父节点变成b
33         if(ran[a]==ran[b]){
34             ran[b]++;
35         }
36     }
37 }
38 
39 int main()  
40 {  
41     init();
42     int m[3][2]={{1,2},{2,3},{4,5}};
43     int col = sizeof(m[0])/sizeof(int); //计算列数
44     int row = (sizeof(m)/sizeof(int))/col; //计算行数
45     int i,j,sum = 0;
46     for(i = 0; i< row; i++){
47         j=0;
48         while(j<col){
49             unionSet(m[i][j],m[i][j++]); //输入原始关系
50             j++;
51         }       
52     }
53     for(i = 1; i<MAX; i++){
54         cout<<"i:"<<i<<" father:"<<father[i];
55         cout<<" rank:"<<ran[i]<<'
';
56         if(findSet(i)==i) sum++; //找有几个根节点，就是有几个朋友圈
57     }
58     cout<<"sum: "<<sum<<endl;      
59 }

输出：

1 Finished in 0 ms
2 i:1 father:1 rank:1
3 i:2 father:1 rank:0
4 i:3 father:1 rank:0
5 i:4 father:4 rank:1
6 i:5 father:4 rank:0
7 sum: 2

6. 课堂作业

思路：老师也没说要做什么操作，然后又说不成环，我猜想就是如果成环的话，就没有父节点了。

 1 int main()  
 2 {  
 3     init();
 4     int m[5]={1,2,3,4,5};
 5     //cout<<col;
 6     int i,j,sum = 0;
 7     for(i = 0; i<5-1; i++){
 8         unionSet(m[i],m[i+1]);
 9     }       
10     for(i = 1; i<MAX; i++){
11         cout<<"i:"<<i<<" father:"<<father[i];
12         cout<<" rank:"<<ran[i]<<'
';
13         if(findSet(i)==i) sum++; //做了路径压缩
14     }
15     cout<<"sum: "<<sum<<endl;      
16 }

输出：

1 i:1 father:2 rank:0
2 i:2 father:2 rank:1
3 i:3 father:2 rank:0
4 i:4 father:2 rank:0
5 i:5 father:2 rank:0
6 sum: 1

sum应该是要>0吧。。。先这样记录，等学习到后面再来更新~