1.8k views

The most efficient algorithm for finding the number of connected components in an undirected graph on $n$ vertices and $m$ edges has time complexity

1. $\Theta(n)$
2. $\Theta(m)$
3. $\Theta(m+n)$
4. $\Theta(mn)$
edited | 1.8k views
+1
Either  BFS or DFS both can do it in $\theta(m+n)$ time.

Run DFS to find connected components. Its time complexity is $\Theta(m+n)$, hence (C) is the answer.

edited by
+5

The explanation of this ans can be find in :

see first 15 minuets portion

### Hence C is Ans

+5
$\Theta (m+n)$ when BFS and DFS is implemented using adjacency list, else it is $\Theta (n^2)$ when implemented using adjacency matrix.
–1 vote
+1
+2
Question asks for connected components in an undirected graph, you have given reference for finding strongly connected components in a directed graph.
+1
ok... but is it really effect ? i mean we cant use for undirected graph ...

see this ...

http://www.geeksforgeeks.org/strongly-connected-components/
+2
This is an overkill for undirected graphs. For undirected graphs, you need to run DFS just once.
0
ok ok....  Thank you ... :)
0