Count Components

Last Updated on March 21, 2022 by Ria Pathak

Concepts Used

Depth First Search, Disjoint Set

Difficulty Level

Easy

Problem Statement :

Given an undirected graph, print Yes if a cycle is present in the graph else print No.

See original problem statement here

Solution Approach :

Introduction :

By definition,
" Connected components in a graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph. A vertex with no incident edges is itself a component. A graph that is itself connected has exactly one component, consisting of the whole graph."

This problem can be solved by many ways like Breadth First Search, Depth First Search or Disjoint Set. Idea is to keep count of the number of connected components. Below we are going to discuss two of the above mentioned methods to solve this problem.

Method 1 (Using DFS) :

In this method we are going to use Depth First Search or DFS to find total number of connected components. In dfs(), we are going to traverse all the adjacent vertices which are not yet visited and mark them as visited so we won’t traverse them again. We have to keep count of the different dfs() calls made for each unvisited vertex and increment count by 1 for each call.
We can keep track if the node is visited or not, using a boolean visited[ ] array of size n which is initially set false (why ?).

Now the question arise, why are we counting the different calls made to dfs() ? The answer lies in the fact that each time we call our dfs() function with some vertex v, it marks all vertices which are connected to v as visited, which means the we are visiting the vertices which are directly or indirectly connected to the v and by the definition of the Connected Component above, this is considered as one component. So each call made up to dfs() with some unvisited vertex v, gives us the different connected component.

Method 2 (Using Disjoint Set) :

Disjoint Set Union or DSU data structure is also sometimes called Union-Find Set. This data structure is used to keep track of the different disjoint sets.
It basically performs two operations :

1. Union : It takes two vertices and join them in a single set (if it is not already there).
2. Find : Determines in which subset the element is.

We will use a parent[] array to keep track of the parents of each vertex. ith element will store the root/parent of i^th vertex. Now we will perform union() for every edge (uv) and update the parent[] array.
Now, iterate for all vertices, for each vertex v, we will find root of v using find() and keep track of all distinct roots. Every time we encounter a distinct root increment the counter by 1.

Each disjoint set stores the vertices which are connected (directly or indirectly) to each other and has no relation/connection with any other vertex (as it is non overlapping set), which means each set itself represents a connected component of the graph and since each set contains exactly one vertex as its root, the sum of distinct roots of all sets gives us the total number of connected components in the graph.

Algorithms :

dfs() :

1. For each call, for some vertex v ( dfs(v) ), we will mark the vertex v as visited (visited[v]= true).
2. Iterate for all the adjacent vertices of v and for every adjacent vertex a, do following :
   • if a is not visited i.e visited[a]= false,
   • recursively call dfs (a).

union() :

1. For two vertices u & v, find the root for both vertices using find() (a=find(u) & b = find(v)).
2. If the root of u & v are not similar, check the level of a & b as follows:
   • if (level[a]>level[b]), update parent[b] = a.
   • else , update parent[b]=a & update level[a] = level[a]+1

find() :

1. If (parent[v]==v), returns the vertex v (which is root).
2. Else, update parent[v] by recursively looking up the tree for the root. (find(parent[v])).

Complexity Analysis:

The time complexity of Depth First Search is represented in the form of O(V + E), where V is the number of nodes and E is the number of edges.

The space complexity of the algorithm is O(V) as it requires one array ( visited[ ]) of size V.

Talking about Union-Find data structure, since we have used path compression & union by rank (refer to Disjoint Set article for more detailed explanation), we will reach nearly constant time O(1) for each query. It turns out, that the final amortized time complexity is O(α(V)), where α(V) is the inverse Ackermann function, which grows very slowly (α(V)<5). In our case a single call might take O(logn) in the worst case, but if we do m such calls back to back we will end up with an average time of O(α(n)).

Solutions:

#include
    #include

    long int findd(long int parent[],int i)
    {
    if(parent[i]==i)
    {
        return i;
    }

    return parent[i] = findd(parent,parent[i]);
    }

    void unionn(long int parent[],long int level[],int i,int j)
    {
    long int a = findd(parent,i);
    long int b = findd(parent,j);

    if(level[a] < level[b])
    parent[a] = b;
    else if(level[a] > level[b])
    parent[b] = a;
    else
    {
        parent[b] = a;
        level[a]++;
    }
    }

    int main()
    {
    int t;
    scanf("%d",&t);

    while(t--)
    {
        int n,e;
        scanf("%d %d",&n,&e);
        long int parent[n],level[n],hash[n];

        for(long int i=0;i0)
        count++;
        }

        printf("%d\n",count);
    }

    return 0;
    }

#include <bits/stdc++.h>
            using namespace std;

        int findd(long int parent[],int i)
        {
          if(parent[i]==i)
          {
          c++;
          return i;
          }

          return parent[i] = findd(parent,parent[i]);
        }

        void unionn(long int parent[],long int level[],int i,int j)
        {
          long int a = findd(parent,i);
          long int b = findd(parent,j);

          if(level[a] < level[b])
          parent[a] = b;
          else if(level[a] > level[b])
          parent[b] = a;
          else
          {
          parent[b] = a;
          level[a]++;
          }
        }

        int main()
        {
          int t;
          cin>>t;

          while(t--)
          {
          int n,e;
          cin>>n>>e;
          long int parent[n],level[n];

          for(long int i=0;i<n;i++)
          {
          parent[i]=i;
          level[i]=0;
          }
          while(e--)
          {
          int u,v;
          cin>>u>>v;

          unionn(parent,level,u,v);
          }
          set<long int> s;
          for(int i=0;i<n;i++)
          s.insert(findd(parent,i));
          cout<<s.size()<<endl;
          }

          return 0;
        }

 import java.util.*; 

    class Main { 

    int V; 
    LinkedList[] adjListArray; 
    int c = 0;

    // constructor 
    Graph(int V) { 
        this.V = V; 
        // define the size of array as 
        // number of vertices 
        adjListArray = new LinkedList[V]; 

        // Create a new list for each vertex 
        // such that adjacent nodes can be stored 

        for(int i = 0; i < V ; i++){ 
            adjListArray[i] = new LinkedList(); 
        } 
    } 

    // Adds an edge to an undirected graph 
    void addEdge( int src, int dest) { 
        // Add an edge from src to dest. 
        adjListArray[src].add(dest); 
        adjListArray[dest].add(src); 
    } 

    void DFSUtil(int v, boolean[] visited) { 
        // Mark the current node as visited and print it 
        visited[v] = true; 
        //System.out.print(v+" "); 
        // Recur for all the vertices 
        // adjacent to this vertex 
        for (int x : adjListArray[v]) { 
            if(!visited[x]) DFSUtil(x,visited); 
        } 

    } 
    int connectedComponents() { 
        // Mark all the vertices as not visited 
        boolean[] visited = new boolean[V]; 
        for(int v = 0; v < V; ++v) { 
            if(!visited[v]) { 
                c++;
                DFSUtil(v,visited); 
            } 
        } 
        return c;
    } 


    public static void main(String[] args){ 
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-->0)
        {
          int n = sc.nextInt();
          int e = sc.nextInt();
          Graph g = new Graph(n); 
          while(e-->0)
          {
            int u = sc.nextInt();
            int v = sc.nextInt();
            g.addEdge(u,v); 
          }

          System.out.println(g.connectedComponents()); 
        }

      } 
    }      

So, in this blog, we have tried to explain Depth First Search, Disjoint Set. If you want to solve interview coding questions, which are curated by our expert mentors at PrepBytes, you can follow this link interview coding.