# 323.Number-of-Connected-Components-in-an-Undirected-Graph

## ้ข็ฎๅฐๅ

https://leetcode.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.

## ไปฃ็ 

### Approach #1 DFS

class Solution {
public int countComponents(int n, int[][] edges) {
if (n <= 1)     return n;
Map<Integer, List<Integer>> map = new HashMap();
for (int i = 0; i < n; i++) {
map.put(i, new ArrayList());
}
for (int[] edge: edges) {
}
Set<Integer> visited = new HashSet();
int count = 0;
for (int i = 0; i < n; i++) {
dfs(i, map, visited);
count++;
}
}
return count;
}

private void dfs(int i, Map<Integer, List<Integer>> map, Set<Integer> visited) {
for (int j : map.get(i)) {