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

分析

很明显的并查集。

class Solution {
public:
    int p[200010];
    int find(int x){
        if(p[x]!=x)p[x]=find(p[x]);
        return p[x];
    }
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        for(int i=0;i<n;i++)p[i]=i;
        for(auto e:edges){
            int a=find(e[0]), b=find(e[1]);
            if(a!=b)p[a]=e[1];
        }
        int s=find(source),d=find(destination);
        return s==d;
    }
};