力扣（LeetCode）323. 无向图中连通分量的数目（2022.11.20）

你有一个包含 n 个节点的图。给定一个整数 n 和一个数组 edges ，其中 edges[i] = [ai, bi] 表示图中 ai 和 bi 之间有一条边。

返回 图中已连接分量的数目 。

示例 1:

输入: n = 5, edges = [[0, 1], [1, 2], [3, 4]]
输出: 2

示例 2:

输入: n = 5, edges = [[0,1], [1,2], [2,3], [3,4]]
输出: 1

提示：

1 <= n <= 2000
1 <= edges.length <= 5000
edges[i].length == 2
0 <= ai <= bi < n
ai != bi
edges 中不会出现重复的边

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/number-of-connected-components-in-an-undirected-graph

方法一：DFS

C++提交内容：

class Solution {
public:
    set<int>check;
    map<int,vector<int>>path;
    int countComponents(int n, vector<vector<int>>& edges) {
        int sum=0;
        for(auto a:edges)
        {
            path[a[0]].push_back(a[1]);//构建双向无向图
            path[a[1]].push_back(a[0]);
        }
        for(int i=0;i<n;i++)
        {
            if(check.find(i)==check.end())//判断是否访问过
            {
                check.insert(i);
                dfs(i);
                sum++;//计数
            }
        }
        return sum;
    }
    void dfs(int n)
    {
        for(auto a:path[n])
        {
            if(check.find(a)==check.end())
            {
            check.insert(a);
            dfs(a);
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34