专栏首页Michael阿明学习之路LeetCode 323. 无向图中连通分量的数目(并查集)

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

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 第 28 场双周赛(505/2144,前23.6%)

    全国排名: 505 / 2144,23.6%;全球排名: 1944 / 8571,22.7%

    Michael阿明
  • LeetCode 347. 前 K 个高频元素(哈希/优先队列)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/top-k-frequent-elements 著作...

    Michael阿明
  • LeetCode 223. 矩形面积

    Michael阿明
  • codeforces329B(bfs)

    由于猎人事先知道我们行走的路线,所以猎人们可以先走到终点前等待,可以使用bfs预处理出终点到各个点之间的距离,如果猎人到终点的距离小于等于我们从起点到终点的距离...

    dejavu1zz
  • BZOJ3143: [Hnoi2013]游走(期望DP 高斯消元)

    Description 一个无向连通图,顶点从1编号到N,边从1编号到M。  小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当...

    attack
  • 2017.5.20欢(bei)乐(ju)赛解题报告

    预计分数:100+20+50=first 实际分数:20+0+10=gg 水灾(sliker.cpp/c/pas) 1000MS  64MB 大雨应经下了几天雨...

    attack
  • OpenCV图像处理专栏十 | 利用中值滤波进行去雾

    这是OpenCV图像处理专栏的第十篇文章,介绍一种利用中值滤波来实现去雾的算法。这个方法发表于国内的一篇论文,链接我放附录了。

    BBuf
  • 树上莫队算法

    attack
  • 挑战程序竞赛系列(23):3.2折半枚举

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 1545 最简单排序

    个人博客:double.win 1545 最简单排序  时间限制: 1 s  空间限制: 1000 KB  题目等级 : 青铜 Bronze 题解 题目描述 D...

    attack

扫码关注云+社区

领取腾讯云代金券