1.4k 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.4k views
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.

answered by Veteran (11.1k points)
edited by

The explanation of this ans can be find in :

see first 15 minuets portion

### Hence C is Ans

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

see this ...

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