Find connected components in a graph [closed]

Question

If I have an undirected graph (implemented as a list of vertices), how can I find its connected components? How can I use quick-union?

Answer 1

Use depth-first search (DFS) to mark all individual connected components as visited:

dfs(node u)
  for each node v connected to u :
    if v is not visited :
      visited[v] = true
      dfs(v)


for each node u:
  if u is not visited :
    visited[u] = true
    connected_component += 1
    dfs(u)

The best way is to use this straightforward method which is linear time O(n).
Since you asked about the union-find algorithm:

for each node parent[node] = node  

for each node u :
   for each node v connected to u :  
       if findset(u)!=findset(v) :
           union(u,v)  

**I assume you know about how findset and union works **  
for each node if (parent[node] == node)  
    connected_component += 1

Answer 2

For every edge(u,v) find union(u,v) using quick union-find datastructure and find set of each vertex using find(v). Each new set is a connected component in the graph