# 323 Number of Connected Components in an Undirected Graph

## 1. Question

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:
0 3
| |
1 --- 2 4
Given`n = 5`and`edges = [[0, 1], [1, 2], [3, 4]]`, return`2`.
Example 2:
0 4
| |
1 --- 2 --- 3
Given`n = 5`and`edges = [[0, 1], [1, 2], [2, 3], [3, 4]]`, return`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`.

## 2. Implementation

(1) BFS
class Solution {
public int countComponents(int n, int[][] edges) {
if (n <= 1) {
return n;
}
// BFS
List<Set<Integer>> adjList = new ArrayList<>();
for (int i = 0; i < n; i++) {
}
for (int[] edge : edges) {
}
boolean[] visited = new boolean[n];
int count = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
++count;
Queue<Integer> queue = new LinkedList<>();
while (!queue.isEmpty()) {
int curIndex = queue.remove();
visited[curIndex] = true;
for (int nextIndex : adjList.get(curIndex)) {
if (!visited[nextIndex]) {
}
}
}
}
}
return count;
}
}
(2) DFS
class Solution {
public int countComponents(int n, int[][] edges) {
if (n <= 1) {
return n;
}
List<Set<Integer>> adjList = new ArrayList<>();
for (int i = 0; i < n; i++) {
}
boolean[] visited = new boolean[n];
for (int[] edge : edges) {
}
int count = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
++count;
}
}
return count;
}
public void searchComponentByDFS(int node, List<Set<Integer>> adjList, boolean[] visited) {
visited[node] = true;
for (int nextNode : adjList.get(node)) {
if (!visited[nextNode]) {
}
}
}
}
(3) Union Find
class Solution {
public int countComponents(int n, int[][] edges) {
if (n <= 1) {
return n;
}
UnionFind uf = new UnionFind(n);
for (int[] edge : edges) {
uf.union(edge[0], edge[1]);
}
return uf.count;
}
class UnionFind {
int[] sets;
int[] size;
int count;
public UnionFind(int n) {
sets = new int[n];
size = new int[n];
count = n;
for (int i = 0; i < n; i++) {
sets[i] = i;
size[i] = 1;
}
}
public int find(int node) {
while (node != sets[node]) {
node = sets[node];
}
return node;
}
public void union(int i, int j) {
int node1 = find(i);
int node2 = find(j);
if (node1 == node2) {
return;
}
if (size[node1] < size[node2]) {
sets[node1] = node2;
size[node2] += size[node2];
}
else {
sets[node2] = node1;
size[node1] += size[node2];
}
--count;
}
}
}

## 3. Time & Space Complexity

BFS: 时间复杂度O(n)，空间复杂度O(n)
DFS: 时间复杂度O(n)，空间复杂度O(n)
Union Find: 时间复杂度O(n), 空间复杂度O(n)