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

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

- $\Theta(n)$
- $\Theta(m)$
- $\Theta(m+n)$
- $\Theta(mn)$

+21 votes

Best answer

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

–1 vote

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

see this ...

http://www.geeksforgeeks.org/strongly-connected-components/

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 559
- Exam Queries 555
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,932 questions

52,335 answers

182,384 comments

67,817 users