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`

.

**Solution 1:** DFS solution

public int CountComponents(int n, int[,] edges)
{
int count = 0;
var visited = new bool[n];
var dict = new Dictionary<int, List>();
for (int i = 0; i < n; i++)
{
dict[i] = new List();
}
for (int i = 0; i < edges.GetLength(0); i++)
{
var from = edges[i, 0];
var to = edges[i, 1];
dict[from].Add(to);
dict[to].Add(from);
}
for (int i = 0; i < n; i++)
{
if (!visited[i])
{
CountComponentsHelper(n, dict, i, visited);
count++;
}
}
return count;
}
private void CountComponentsHelper(int n, Dictionary<int, List> dict, int cur, bool[] visited)
{
if (visited[cur]) return;
visited[cur] = true;
foreach (var edge in dict[cur])
{
CountComponentsHelper(n, dict, edge, visited);
}
}

**Solution 2:** BFS solution

private void CountComponentsHelper2(int n, Dictionary<int, List> dict, int cur, bool[] visited)
{
if (visited[cur]) return;
var queue = new Queue();
queue.Enqueue(cur);
while (queue.Any())
{
var size = queue.Count;
for (int i = 0; i < size; i++)
{
var top = queue.Dequeue();
if (!visited[top])
{
visited[top] = true;
foreach (var edge in dict[top])
{
queue.Enqueue(edge);
}
}
}
}
}

**Solution 3:** Union Find solution

public int CountComponents2(int n, int[,] edges)
{
var index = Enumerable.Range(0, n).ToList();
for (int i = 0; i < edges.GetLength(0); i++)
{
var from = edges[i, 0];
var to = edges[i, 1];
Union(index, from, to);
}
var count = 0;
var rootset = new HashSet();
for (int i = 0; i < n; i++)
{
if (rootset.Add(FindRoot(index, i)))
{
count ++;
}
}
return count;
}
private void Union(List index, int fr, int to)
{
var frRoot = FindRoot(index, fr);
var toRoot = FindRoot(index, to);
index[toRoot] = index[frRoot];
}
private int FindRoot(List index, int i)
{
while (index[i] != i)
{
i = index[i];
}
return i;
}