**Solutions**

**Number of Connected Components in an Undirected Graph** https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/

**Depth First Search: O(V+E)**

- Build a graph using the list of edges. Maintain a set called visited to track the nodes which have been visited so far.
- Iterate through all vertices and call DFS on each unvisited vertex. The DFS on that vertex will mark all reachable nodes with that vertex. That constitutes a component abd we increment the count for components.

```
class G(object):
def __init__(self, n, edges):
self.nbr = {}
for i in range(n):
self.nbr[i] = []
for edge in edges:
u, v = edge[0], edge[1]
self.nbr[u].append(v)
self.nbr[v].append(u)
return
def adj(self, u):
return self.nbr[u]
class Solution(object):
def dfs(self, v, visited, g):
visited.add(v)
for nbr in g.adj(v):
if nbr not in visited:
self.dfs(nbr, visited, g)
return
def countComponents(self, n, edges):
"""
:type n: int
:type edges: List[List[int]]
:rtype: int
"""
g = G(n, edges)
visited = set([])
components = 0
for v in range(n):
if v not in visited:
self.dfs(v, visited, g)
components += 1
return components
```