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.4k views answer comment Share Follow See all 4 Comments See all 4 4 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 cprdereddyy commented 5 days ago reply Follow Share thoose who don't know what CC arevisit this for a clear approachhttps://www.youtube.com/watch?v=8f1XPm4WOUc 0 votes 0 votes Please log in or register to add a comment.
Best answer 29 votes 29 votes Run DFS to find connected components. Its time complexity is $\Theta(m+n)$, hence (C) is the answer. Happy Mittal answered Aug 22, 2015 • edited Oct 26, 2017 by kenzou Happy Mittal comment Share Follow See all 25 Comments See all 25 25 Comments reply Show 22 previous comments Sambhrant Maurya commented Dec 9, 2019 i edited by ankitgupta.1729 Dec 9, 2019 reply Follow Share @Aks9639 Yes found it. There is no such thing as "connected components" in a directed graph. We use the term "connected components" for undirected graphs and "strongly connected components" for directed graphs. Finding strongly connected components in a directed graph is given by Kosaraju's algo which is an application of DFS. So TC is O(V+E). 3 votes 3 votes Abhrajyoti00 commented Dec 11, 2022 reply Follow Share Both BFS and DFS can be used to find in $O(m+n)$ :- Undirected Graph:- Single connected component or not # Of Connected Components in G Single Bi-Connected Component or not # of Bi-Connected Components in G Directed Graph: - Single weakly connected component or not # Of weakly Connected Components in G Single strongly connected Component or not # Of strongly connected Components 1 votes 1 votes sitikant commented Aug 25, 2023 reply Follow Share Although both BFS and DFS can be used. Still DFS is preferred from memory stand points. Give it a read : https://cs.stackexchange.com/questions/73686/why-do-we-prefer-dfs-to-find-connected-components. 0 votes 0 votes Please log in or register to add a comment.
24 votes 24 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 Rajesh Pradhan answered Nov 10, 2016 Rajesh Pradhan comment Share Follow See all 2 Comments See all 2 2 Comments reply habedo007 commented Oct 23, 2017 reply Follow Share $\Theta (m+n)$ when BFS and DFS is implemented using adjacency list, else it is $\Theta (n^2)$ when implemented using adjacency matrix. 10 votes 10 votes syncronizing commented Aug 21, 2018 reply Follow Share Or we can say Max(m,n) 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes To find the number of connected components using either BFS or DFS time complexity is θ(m+n). Suppose if we are using Adjacency matrix means it takes θ(n2). varunrajarathnam answered Aug 7, 2020 varunrajarathnam comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes BFS and DFS is used for traversing the graph which takes O(m+n). Surya_Dev Chaturvedi answered Jan 15, 2021 Surya_Dev Chaturvedi comment Share Follow See all 0 reply Please log in or register to add a comment.