1971. 寻找图中是否存在路径-并查集基础

Problem: 1971. 寻找图中是否存在路径

Reference

并查集理论基础
1971. 寻找图中是否存在路径

思路

本题目思路就是并查集。

路径压缩：

并查集的思想上面链接已经讲的非常清楚了,我不在赘述。

这里提几个代码的易错点。

1. 申明father数组

这里不知为何只能这样声明：

int n = 200005;
vector<int> father = vector<int>(n, 0);

这样申明会报错：

vector<int> father(20005, 0);

2. for循环

在使用 for (vector<int> item : edges) 循环遍历边的时候，最好使用引用来避免不必要的复制开销。修改为 for (vector<int>& item : edges)。

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]

class Solution {
public:
    int n = 200005;
    vector<int> father = vector<int>(n, 0);
    void init() {
        for (int i = 0; i < father.size(); i++) {
            father[i] = i;
        }
    }
    void join(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v)
            return;
        father[v] = u;
    }
    int find(int u) {
        if (u == father[u])
            return u;
        // else return find(father[u]);
        else {
            father[u] = find(father[u]);
            return father[u];
        }
    }
    bool isSame(int u, int v) {
        u = find(u);
        v = find(v);
        return u == v;
    }
    bool validPath(int n, vector<vector<int>>& edges, int source,
                   int destination) {
        init();
        for (vector<int>& item : edges) {
            join(item[0], item[1]);
        }
        return isSame(source, destination);
    }
};