Leetcode 261. 以图判树(中等) 1135. 最低成本联通所有城市(中等) 1584. 连接所有点的最小费用(中等) 并查集&Kruskal最小生成树

思路讲解

261. 以图判树(中等)

题目:

给定编号从 0 到 n - 1 的 n 个结点。给定一个整数 n 和一个 edges 列表,其中 edges[i] = [ai, bi] 表示图中节点 ai 和 bi 之间存在一条无向边。

如果这些边能够形成一个合法有效的树结构,则返回 true ,否则返回 false 。

示例 1:

 

输入: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
输出: true
示例 2:

 

输入: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
输出: false

因为包含了环

思路:

使用并查集,当一条边的两个节点已经处于联通状态时,新加的边就肯定构成了环。

对于添加的这条边,如果该边的两个节点本来就在同一连通分量里,那么添加这条边会产生环;反之,如果该边的两个节点不在同一连通分量里,则添加这条边不会产生环

class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        UF uf(n);
        // 遍历所有边,将组成边的两个节点进行连接
        for(int i=0;i<edges.size();++i){
            int p=edges[i][0];
            int q=edges[i][1];
            // 若两个节点已经在同一连通分量中,会产生环
            if(uf.connected(p,q)){
                return false;
            }
            // 这条边不会产生环,可以是树的一部分
            uf.Union(p,q);
        }
        // 要保证最后只形成了一棵树,即只有一个连通分量
        return uf.count==1;
    }
class UF{
public:
    UF(int n){
        count=n;
        for(int i=0;i<n;++i){
            parent.push_back(i);
            size.push_back(1);
        }
    }
    void Union(int p,int q){
        int rootp=find(p);
        int rootq=find(q);
        if(rootp==rootq){
            return;
        }
        if(size[rootp]>size[rootq]){
            size[rootq]+=size[rootp];
            parent[rootp]=rootq;
        }else{
            size[rootq]+=size[rootp];
            parent[rootq]=rootp;
        }
        count--;
    }
    int find(int x){
        while(x!=parent[x]){
            parent[x]=parent[parent[x]];
            x=parent[x];
        }
        return x;
    }
    bool connected(int p,int q){
        int rootp=find(p);
        int rootq=find(q);
        return rootp==rootq;
    }
    int count;
    vector<int> parent;
    vector<int> size;
};
};

 

 

1135. 最低成本联通所有城市(中等)

题目:

Leetcode 261. 以图判树(中等)  1135. 最低成本联通所有城市(中等)  1584. 连接所有点的最小费用(中等) 并查集&Kruskal最小生成树

 

 思路:

1、包含图中的所有节点。

2、形成的结构是树结构(即不存在环)。

3、权重和最小。

前两点用并查集来判断,第三点使用贪心:

将所有边按照权重从小到大排序,从权重最小的边开始遍历,如果这条边和mst中的其它边不会形成环,则这条边是最小生成树的一部分,将它加入mst集合;否则,这条边不是最小生成树的一部分,不要把它加入mst集合

 

class Solution {
public:
    int minimumCost(int n, vector<vector<int>>& connections) {
        // 城市编号为 1...n,所以初始化大小为 n + 1
        UF uf(n+1);
        // 对所有边按照权重从小到大排序
        sort(connections.begin(),connections.end(),
            [](const vector<int>& a, const vector<int>& b){
                return a[2]<b[2];
            });
        // 记录最小生成树的权重之和
        int sum=0;
        for(int i=0;i<connections.size();++i){
            int p=connections[i][0];
            int q=connections[i][1];
            int cost=connections[i][2];
            // 若这条边会产生环,则不能加入 mst
            if(uf.connected(p,q)){
                continue;
            }
            // 若这条边不会产生环,则属于最小生成树 
            sum+=cost;
            uf.Union(p,q);
        }
        // 保证所有节点都被连通
    // 按理说 uf.count() == 1 说明所有节点被连通
    // 但因为节点 0 没有被使用,所以 0 会额外占用一个连通分量
        return uf.count==2?sum:-1;
    }
class UF{
public:
    UF(int n){
        count=n;
        for(int i=0;i<n;++i){
            parent.push_back(i);
            size.push_back(1);
        }
    }
    void Union(int p,int q){
        int rootp=find(p);
        int rootq=find(q);
        if(rootp==rootq)
            return;
        parent[rootp]=rootq;
        count--;
    }
    int find(int x){
        while(x!=parent[x]){
            parent[x]=parent[parent[x]];
            x=parent[x];
        }
        return x;
    }
    bool connected(int p, int q){
        int rootp=find(p);
        int rootq=find(q);
        return rootp==rootq;
    }
    int count;
    vector<int> parent;
    vector<int> size;
};
};

 

 

1584. 连接所有点的最小费用(中等)

题目:

Leetcode 261. 以图判树(中等)  1135. 最低成本联通所有城市(中等)  1584. 连接所有点的最小费用(中等) 并查集&Kruskal最小生成树

 

 

思路:

很显然这也是一个标准的最小生成树问题:每个点就是无向加权图中的节点,边的权重就是曼哈顿距离,连接所有点的最小费用就是最小生成树的权重和。

所以解法思路就是先生成所有的边以及权重,然后对这些边执行 Kruskal 算法即可:

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        vector<vector<int>> graph;
        int n=points.size();
        // 生成所有边及权重
        for(int i=0;i<n;++i){
            for(int j=i+1;j<n;++j){
                int xi=points[i][0];
                int yi=points[i][1];
                int xj=points[j][0];
                int yj=points[j][1];
                int cost=abs(xi-xj)+abs(yi-yj);
                // 用坐标点在 points 中的索引表示坐标点
                graph.push_back({i,j,cost});
            }
        }
        UF uf(n);
        // 将边按照权重从小到大排序
        sort(graph.begin(),graph.end(),
            [](const vector<int>& a, const vector<int>& b){
                return a[2]<b[2];
            });
        // 执行 Kruskal 算法
        int sum=0;
        for(int i=0;i<graph.size();++i){
            int p=graph[i][0];
            int q=graph[i][1];
            int cost=graph[i][2];
            // 若这条边会产生环,则不能加入 mst
            if(uf.connected(p,q)){
                continue;
            }
            // 若这条边不会产生环,则属于最小生成树
            sum+=cost;
            uf.Union(p,q);
        }
        return sum;
    }
class UF{
public:
    UF(int n){
        count=n;
        for(int i=0;i<n;++i){
            parent.push_back(i);
            size.push_back(1);
        }
    }
    void Union(int p, int q){
        int rootp=find(p);
        int rootq=find(q);
        if(rootp==rootq) return;
        parent[rootp]=rootq;
    }
    int find(int x){
        while(x!=parent[x]){
            parent[x]=parent[parent[x]];
            x=parent[x];
        }
        return x;
    }
    bool connected(int p, int q){
        int rootp=find(p);
        int rootq=find(q);
        return rootp==rootq;
    }
    int count;
    vector<int> parent;
    vector<int> size;
};
};

 

上一篇:数据结构之红黑树。2-3-4树


下一篇:B/S上传整个文件夹