## 5 Answers

### 23 Comments

@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.

But if we talk in terms of complexity then prims and kruskal both take $O(m\log n)$ time. And if graph is dense then m=n(n-1)/2 (for complete graph).

Here our intention is not to calculate minimum cost (or mst) , and finding minimum edge(sorting) is going to increase complexity in prim/kruskal.

I think DFS and BFS both work for `unweighted graph`

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

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

Where as kruskal, prims takes $\Theta \left ( mn \right )$ in worst case,

Which is much larger time than BFS and DFS.

Sorry mam, i don't remember exact algos and forget some concepts.. So i think i have to revise Algorithm.

You can refer →_→

https://cs.stackexchange.com/questions/10047/is-dijkstras-algorithm-just-bfs-with-a-priority-queue

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

@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).

### 6 Comments

see this ...

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