# 323. Number of Connected Components in an Undirected Graph 无向图中连通分量的数目

@TOC

## # 题目描述

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.

## # 解题方法

### # 并查集

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 日 —— 熬夜废掉半条命