文档章节

LeetCode 323. 无向图中连通分量的数目(并查集)

o
 osc_lk0wespa
发布于 07/07 16:54
字数 370
阅读 48
收藏 0

行业解决方案、产品招募中!想赚钱就来传!>>>

文章目录

1. 题目

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

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

     0          3
     |          |
     1 --- 2    4 

输出: 2

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

     0           4
     |           |
     1 --- 2 --- 3

输出:  1

注意:
你可以假设在 edges 中不会出现重复的边。
而且由于所以的边都是无向边,[0, 1][1, 0]  相同,所以它们不会同时在 edges 中出现。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/number-of-connected-components-in-an-undirected-graph 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

参考:并查集

class dsu
{
public:
    vector<int> f;
    dsu(int n)
    {
        f = vector<int>(n);
        for(int i = 0; i < n; ++i)
            f[i] = i;
    }
    void merge(int a, int b)
    {
        int fa = find(a);
        int fb = find(b);
        f[fa] = fb;
    }
    int find(int a)
    {
        int origin = a;
        while(a != f[a])
            a = f[a];
        return f[origin] = a;
    }
    int countUni()
    {
        int count = 0;
        for(int i = 0; i < f.size(); ++i)
        {
            if(i == find(i))
                count++;
        }
        return count;
    }
};
class Solution {
public:
    int countComponents(int n, vector<vector<int>>& edges) {
        dsu u(n);
        for(auto& e : edges)
            u.merge(e[0],e[1]);
        return u.countUni();
    }
};

32 ms 10.9 MB


我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号(Michael阿明),一起加油、一起学习进步!
Michael阿明

o
粉丝 0
博文 68
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
CSS 选择器--Q.js

1, 和Sizzle的兼容 Q(expr, context, result, seed) Q.matches 支持Sizzle特别的setFilter伪类如:even,:first,:last,:lt... 支持复杂的:not和:has选择器(和sizzle一样) 2, 结果的正确性 Si...

hackwaly
2012/10/23
4.6K
0
AngularJS 的UI增强指令集--AngularUI

Angular UI 顾名思义,AngularJS 的UI增强指令集,提供了IE、jQuery 兼容,以及一些常用 UI 组件。 包含的模块有: UI-Utils UI-Modules UI-Alias UI-Bootstrap NG-Grid UI-Router IDE Plug...

匿名
2012/12/24
4.2W
0
Arduino 兼容开发板--Microduino

Microduino 是 Arduino 的兼容开发板。 Microduino 采用 U 型 27pin Microduino 接口规范,尺寸小巧,长25.4mm X 宽27.94mm,仅一枚1元人民币硬币的大小。轻量化的设计让Microduino在对尺寸、...

匿名
2013/05/14
8.1K
0
LKDBHelper Sqlite ORM

这是一个sqlite ORM(automatic database operation),能够根据 Model的属性自动生成表和进行增删改查操作。对于每个实体类 几乎是 零操作。 开发者不用再一行行写插入、修改、删除的SQL代码...

匿名
2013/05/21
1.6K
0
DephtInition

使用微软Kinect平台进行3D扫描是一种常见方法,如今计算机工程师吉安卡洛已经找到了一种新的方式:使用对焦堆叠。这个概念被称为焦点深度,通常使 用在显微镜中。吉安卡洛将其进行了简化,设...

troika
2013/06/30
2K
1

没有更多内容

加载失败,请刷新页面

加载更多

2020年西安未来五年哪些编程语言更有发展前景

西安作为一线城市,随着5G标准的落地应用,未来五年产业互联网将逐渐落地到广大的传统行业,以辅助传统行业的结构性升级。产业互联网的核心技术包括大数据、云计算、物联网和人工智能等技术,...

osc_4eht81t7
30分钟前
0
0
三网竞对测试仪在多网室分中的应用(移动网络竞对测试)

三网竞对测试仪在多网室分中的应用 现代城市的高楼大厦,栉次鳞比,一片繁华的背后是室分人的焦虑,随着网络的发展室分系统更注重精细化的室内覆盖及优化,系统指标不仅要关注场强覆盖,而且...

osc_k3vwonkw
31分钟前
0
0
B的时代过去了,新的时代已经来临

BAT中的B的时代基本上已经过去了,看起来是败于移动时代,但本质是传统的文字搜索已经到了顶峰,走下坡路了。百度没有抓住移动互联网,也没有抓住视频时代,这里面,其实也包括谷歌,谷歌比百...

osc_mzickfah
33分钟前
0
0
OSP单区域通信(骨干区域)

第一步设置IP地址 R1 undo terminal monitor [Huawei]user-interface console 0 [Huawei-ui-console0]idle-timeout 0 0 [Huawei]sysname R1 [R1]int g0/0/0 [R1-GigabitEthernet0/0/0]ip add......

osc_m6gaz63w
34分钟前
28
0
5G来电奥秘

5G 电话是怎样传播声音的? The number you are trying to reach is turned off ! 电话是怎样传播声音的? 首先,电话有bai一个听筒和一个话筒,话筒内有du一个磁圈可以将人的声波转化zhi为...

osc_kvlhvh2u
34分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部