​LeetCode刷题实战323:无向图中连通分量的数目

程序IT圈

共 2902字,需浏览 6分钟

 ·

2021-07-18 11:19

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 无向图中连通分量的数目,我们先来看题面:
https://leetcode-cn.com/problems/number-of-connected-components-in-an-undirected-graph/

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

给定编号从 0 到 n-1 的 n 个节点和一个无向边列表(每条边都是一对节点),请编写一个函数来计算无向图中连通分量的数目。


示例



解题

https://blog.csdn.net/Scarlett_Guan/article/details/104086040
这个题目可以转化为用并查集求一共有多少个老大的问题。

class Solution {
public:
    //找每一个顶点的老大
    int find_father(vector<int> &f, int i){
        while(i!=f[i]){
            i=f[i];
        }
        return i;
    }
 
    int countComponents(int n, vector<vector<int>>& edges) {
        vector<int>f(n);
        //将每一个顶点单独分成一组
        for(int i=0; i<n; ++i){
            f[i]=i;
        }
        //进行同一组的顶点的合并
        for(auto x:edges){
            int p=find_father(f, x[0]);
            int q=find_father(f, x[1]);
            if(p==q) continue;
            else f[p]=q;
        }
        //找一共有多少个不同的老大
        unordered_set<int>s;
        for(int i=0; i<f.size(); ++i){
            s.insert(find_father(f, i));
        }
        return s.size();
    }
};


好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:
LeetCode1-320题汇总,希望对你有点帮助!
LeetCode刷题实战321:拼接最大数
LeetCode刷题实战322:零钱兑换

浏览 16
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报