代码随想录打卡Day59

今天进入了查并集部分，感觉在原理学习部分没有特别难理解的地方，今天只有一道练习题，因为还不太熟悉整个流程，所以直接套用模板，把要用到的一系列函数直接复制粘贴上去，然后直接写主函数，明天的题目尝试着自己写基础功能函数。

并查集理论

并查集常用来解决连通性问题。当我们需要判断两个元素是否在同一个集合里的时候，我们就要想到用并查集。查并集的功能主要有两个：1.将两个元素添加到一个集合中；2.判断两个元素在不在同一个集合。查并集首先需要先定义几个功能函数：
1.father数组初始化函数，在尚未获取到节点之间的连通信息时，我们先默认每个节点只和自己连通，只和自己在一个集合中，因此father[i] = i;

// 并查集初始化
void init(vector<int> &father) {
    for (int i = 1; i < father.size(); i++) {
        father[i] = i;
    }
}

2.寻根函数，这个函数的主要作用是查询某个节点的根节点并返回，实际上也是一个递归函数。这里有基础版和路径压缩版。

// 并查集里的寻根函数（基础版）
int find(int u) {
    if (u == father[u]) return u; // 如果根就是自己，直接返回
    else return find(father[u]); // 如果根不是自己，就根据数组下标一层一层向下找
}

// 并查集里的寻根函数（路径压缩版，节点直接一步到位定位到根节点）
int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
}

3.加入并查集函数，这个函数的主要作用是将一条连通边上的两个节点各自的父节点加入并查集，说得更直白点，就是将两个节点的根节点连通，而不是直接连通这两个节点。

// 将v，u 这条边加入并查集
void join(int u, int v) {
    u = find(u); // 寻找u的根
    v = find(v); // 寻找v的根
    if (u == v) return; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
    father[v] = u;
}

4.判断是否为同一根节点函数，这个函数主要作用是判断两个节点的根节点是否相同（也就是是否在同一集合），如果相同返回true，否则返回false。

// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

在做并查集这类题目时，需要先把上面四个函数（四部曲）先写好，再写主函数逻辑。

107. 寻找存在的路径

这个题目是基础题，只要之前的四个函数写出来了，然后在读取中间的M条边的过程中不断调用join函数构建并查集，在构建完成后直接调用isSame函数判断source和destination是否在同一集合，如果是，输出1，否则输出0.

#include<iostream>
#include<vector>

using namespace std;

void init(vector<int> &father);
int find(int u, vector<int> &father);
bool isSame(int u, int v, vector<int> &father);
void join(int u, int v, vector<int> &father);

int main(){
    int N, M;
    cin >> N >> M;
    vector<int> father(N + 1);
    int source, destination;
    cin >> source >> destination;
    init(father);   //初始化
    for(int i = 1; i <= M; i++){
        int s, t;
        cin >> s >> t;
        join(s, t, father);
    }
    int result = isSame(source, destination, father) ? 1 : 0;
    cout << result << endl;
    return 0;
}

// 并查集初始化
void init(vector<int> &father) {
    for (int i = 1; i < father.size(); i++) {
        father[i] = i;
    }
}
// 并查集里寻根的过程
int find(int u, vector<int> &father) {
    return u == father[u] ? u : father[u] = find(father[u], father); // 路径压缩
}
// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v, vector<int> &father) {
    u = find(u, father);
    v = find(v, father);
    return u == v;
}
// 将v->u 这条边加入并查集
void join(int u, int v, vector<int> &father) { 
    u = find(u, father); // 寻找u的根
    v = find(v, father); // 寻找v的根
    if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
    father[v] = u;
}

奥力给！加油加油！💪