GATE2008-7

Question

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

• A. $\Theta(n)$
• B. $\Theta(m)$
• C. $\Theta(m+n)$
• D. $\Theta(mn)$

Comments

Either  BFS or DFS both can do it in $\theta(m+n)$ time.

---

But then we can use disjoint sets to find the number of connected components. Its time complexity is only O(m). Why not option B??

Answer 1

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

Comments

The explanation of this ans can be find in :

see first 15 minuets portion 

 

---

---

But then we can use disjoint sets to find the number of components. Its time complexity is only O(m). Why not option B??

---

@Vivek Jain can you explain how to use disjoint sets?? I'm not getting what is your approach??

According to me it should be O(m+n) by using dfs or bfs.

 

Answer 2

Both BFS or DFS can be used to find number of connected components.

The Time complexity of BFS and DFS is $\Theta$(m+n).

Hence C is Ans

Comments

$\Theta (m+n)$ when BFS and DFS is implemented using adjacency list, else it is $\Theta (n^2)$ when implemented using adjacency matrix.

---

Or we can say Max(m,n)

Answer 3

Answer is C.

Comments

ans (c)

https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

---

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 ... :)

---

what about the directed graphs???