The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+16 votes
2.3k 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)$
asked in Algorithms by Veteran (59.9k points)
edited by | 2.3k views
+1
Either  BFS or DFS both can do it in $\theta(m+n)$ time.
0
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??

3 Answers

+21 votes
Best answer

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

answered by Boss (11.3k points)
edited by
+6

The explanation of this ans can be find in :

see first 15 minuets portion 



 


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

@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.

 

+14 votes

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

answered by Boss (23.6k points)
+5
$\Theta (m+n)$ when BFS and DFS is implemented using adjacency list, else it is $\Theta (n^2)$ when implemented using adjacency matrix.
0
Or we can say Max(m,n)
–1 vote
Answer is C.
answered by Boss (19.9k points)
+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
what about the directed graphs???
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
47,932 questions
52,335 answers
182,384 comments
67,817 users