【LeetCode】323. Number of Connected Components in an Undirected Graph 解题报告 (C++)

时间：2022-11-28 14:59:57

题目地址：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.

Example 1:

Input: n = 5 and edges = [[0, 1], [1, 2], [3, 4]]

     0          3

     |          |

     1 --- 2    4 

Output: 2

Example 2:

Input: n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]]

     0           4

     |           |

     1 --- 2 --- 3

Output:  1

Note:

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

题目大意

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

解题方法

并查集

看到求联通分量的题，一般都可以用并查集。比如1101. The Earliest Moment When Everyone Become Friends。

只要把并查集背下来，这个题目基本直接写上去就好了。

C++代码如下：

class Solution {

public:

    int countComponents(int n, vector<vector<int>>& edges) {

        map_ = vector<int>(n, 0);

        components = n;

        for (int i = 0; i < n; ++i) {

            map_[i] = i;

        }

        for (vector<int>& edge : edges) {

            uni(edge[0], edge[1]);

        }

        return components;

    }

    int find(int a) {

        if (a == map_[a])

            return a;

        return find(map_[a]);

    }

    void uni(int a, int b) {

        int pa = find(a);

        int pb = find(b);

        if (pa == pb)

            return;

        map_[pa] = pb;

        components --;

    }

private:

    vector<int> map_;

    int components;

};

日期

2019 年 9 月 22 日 —— 熬夜废掉半条命

相关文章