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

链接：1971.寻找图中是否存在路径
难度：Easy
标签：深度优先搜索、广度优先搜索、并查集、图
简介：请你确定是否存在从顶点 source 开始，到顶点 destination 结束的 有效路径 。

题解 1 - cpp

• 编辑时间：2022-12-19
• 执行用时：304ms
• 内存消耗：109.9MB
• 编程语言：cpp
• 解法介绍：并查集。

class UnionFind {
public:
    int n;
    vector<int> data, cnt;
    UnionFind(int n): n(n), data(vector<int>(n, 0)), cnt(vector<int>(n, 1)) {
        iota(data.begin(), data.end(), 0);
    }
    int size(int v) { return cnt[find(v)]; }
    int find(int v) {
        if (data[v] == v) return v;
        return data[v] = find(data[v]);
    }
    void uni(int v1, int v2) {
        int p1 = find(v1), p2 = find(v2);
        if (p1 != p2) cnt[p1] += cnt[p2], data[p2] = p1;
    }
    bool same(int v1, int v2) { return find(v1) == find(v2); }
};
class Solution {
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        UnionFind uf(n);
        for (auto &edge : edges) uf.uni(edge[0], edge[1]);
        return uf.same(source, destination);
    }
};