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

+14 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)$

+19 votes

Best answer

+13 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.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.2k
- Algorithms 3.6k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.3k
- CO & Architecture 2.9k
- Computer Networks 3.3k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 480
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,748 questions

47,471 answers

145,585 comments

62,234 users