28 votes 28 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)$ Algorithms gatecse-2008 algorithms graph-algorithms time-complexity normal + – Kathleen asked Sep 11, 2014 edited Oct 26, 2017 by kenzou Kathleen 13.2k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Manu Thakur commented Dec 29, 2017 reply Follow Share Either BFS or DFS both can do it in $\theta(m+n)$ time. 6 votes 6 votes Vivek Jain commented Nov 10, 2018 reply Follow Share 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?? 0 votes 0 votes palashbehra5 commented Nov 18, 2021 reply Follow Share Vivek Jain https://www.geeksforgeeks.org/number-of-connected-components-of-a-graph-using-disjoint-set-union/ If you meant this algorithm, it takes O(n+m) time as well. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes (C.) θ(m+n) Rahul_kumar3 answered Oct 18, 2023 Rahul_kumar3 comment Share Follow See all 0 reply Please log in or register to add a comment.
–2 votes –2 votes Answer is C. Gate Keeda answered Dec 11, 2014 Gate Keeda comment Share Follow See all 6 Comments See all 6 6 Comments reply minal commented Aug 21, 2015 reply Follow Share ans (c) https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm 1 votes 1 votes Happy Mittal commented Aug 22, 2015 reply Follow Share Question asks for connected components in an undirected graph, you have given reference for finding strongly connected components in a directed graph. 3 votes 3 votes minal commented Aug 22, 2015 reply Follow Share ok... but is it really effect ? i mean we cant use for undirected graph ... see this ... http://www.geeksforgeeks.org/strongly-connected-components/ 1 votes 1 votes Happy Mittal commented Aug 22, 2015 reply Follow Share This is an overkill for undirected graphs. For undirected graphs, you need to run DFS just once. 2 votes 2 votes minal commented Aug 22, 2015 reply Follow Share ok ok.... Thank you ... :) 0 votes 0 votes ashwani kumar sharma commented Aug 4, 2018 reply Follow Share what about the directed graphs??? 0 votes 0 votes Please log in or register to add a comment.