当前位置：首页 > article >正文

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

article 2025/3/25 21:49:02

初尝并查集，直接套用模板

class Solution {
private:
    vector<int> father;

    void init() {
        for(int i=0;i<father.size();i++)
            father[i]=i;
    }

    int find(int v) {
        return v==father[v]?v:father[v]=find(father[v]);//路径压缩
    }

    bool isSame(int u,int v){
        u=find(u);
        v=find(v);
        return u==v;
    }

    //将v->u这条边加入到并查集中
    void join(int u,int v) {
        u=find(u);
        v=find(v);
        if(u==v) 
            return;
        else
            father[v]=u;
    }
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        father=vector<int>(n);
        this->init();
        for(int i=0;i<edges.size();i++){
            int u=edges[i][0];
            int v=edges[i][1];
            this->join(u,v);
        }
        return this->isSame(source,destination);
    }
};

查看全文

http://www.kler.cn/a/597480.html