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

Michael阿明

发布于 2020-07-13 08:33:40

1.8K00

代码可运行

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

运行总次数：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();
    }
};