323. 无向图中连通分量的数目

323. 无向图中连通分量的数目

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

示例 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 中不会出现重复的边

 1 class Solution {
 2 public:
 3     unordered_map<int, vector<int>> hashMap; // key->节点值,value->与该节点连通节点列表
 4     int countComponents(int n, vectorint>>& edges) {
 5         // 1、构建无向连通图
 6         for (auto &vec : edges) {
 7             hashMap[vec[0]].push_back(vec[1]);
 8             hashMap[vec[1]].push_back(vec[0]);
 9         }
10         // 2、设置访问标记
11         vector<bool> visited(n, false);
12         // 3、广度优先搜索找到连通路径数
13         int count = 0;
14         queue<int> q;
15         for (int i = 0; i < n; i++) {
16             if (visited[i]) {
17                 continue;
18             }
19             q.push(i);
20             visited[i] = true;
21             count++;
22             while (!q.empty()) {
23                 int tmp = q.front();
24                 q.pop();
25                 // 找到与tmp连通且未被访问过的节点入队
26                 for (auto val : hashMap[tmp]) {
27                     if (!visited[val]) {
28                         q.push(val);
29                         visited[val] = true;
30                     }
31                 }
32             }
33         }
34         return count;
35     }
36 };