The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+17 votes

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)$
in Algorithms by Veteran (52.1k points)
edited by | 2.6k views
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??

3 Answers

+23 votes
Best answer

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

by Boss (11.2k points)
edited by


and undirect or directed doesnot matter much for these algos. Right? 

Yes. (And prim and kruskal only work for undirected graph)

And In DFS among vertices and edges , which will be greater will be answer, Means if m>n, ans will be Θ(m) and if m<n ans will be Θ(n). right? 



We can't apply directly prims algorithm to disconnected graph

DFS and BFS algo also doesnot support disconnected graph .

We can apply DFT/BFT (depth first traversal and breadth first traversal)
I havenot got what u mean . Can u explain it clearly?

@Verma Ashish

Dijkstra uses BFS but Dijkstra T.C. more than BFS. Right?

That is why BFS also not a suitable option here. right??

Another question coming here, though Dijkstra uses BFS, but why Dijkstra T.C. greater than BFS?? Can u answer it?


@Verma Ashish @Rajesh Pradhan What if the question was about "directed graphs"? How do we find connected components in a directed graph?

In directed graph same algorithm will work, you get theta(V+E) refer CLRS .
I think that is $(V+E)\log V$??


How you get (V+E) log V ? 

+15 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

by Boss (23.6k points)
$\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)
–2 votes
Answer is C.
by Boss (19.9k 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 ...
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???

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
50,309 questions
55,743 answers
90,496 users