{"id":1876,"date":"2020-07-01T09:47:14","date_gmt":"2020-07-01T09:47:14","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1876"},"modified":"2022-03-21T10:44:54","modified_gmt":"2022-03-21T10:44:54","slug":"count-components","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/count-components\/","title":{"rendered":"Count Components"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Depth First Search, Disjoint Set<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Easy<\/p>\n<\/blockquote>\n

Problem Statement :<\/h3>\n
\n

Given an undirected graph, print Yes if a cycle is present in the graph else print No.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Solution Approach :<\/h3>\n

Introduction<\/strong> :<\/p>\n

\n

By definition,
\n" 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." <\/p>\n

This problem can be solved by many ways like Breadth First Search<\/strong>, Depth First Search<\/strong> or Disjoint Set<\/strong>. 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.<\/p>\n<\/blockquote>\n

\"\"<\/p>\n

Method 1 (Using DFS)<\/strong> :<\/p>\n

\n

In this method we are going to use Depth First Search<\/strong> or DFS<\/strong> to find total number of connected components. In dfs()<\/strong>, 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()<\/strong> calls made for each unvisited vertex and increment count by 1<\/code> for each call.
\nWe can keep track if the node is visited or not, using a boolean visited[ ]<\/strong> array of size n<\/code> which is initially set false (why ?<\/code>).<\/p>\n

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

Method 2 (Using Disjoint Set)<\/strong> :<\/p>\n

\n

Disjoint Set Union<\/strong> or DSU<\/strong> data structure is also sometimes called Union-Find Set<\/strong>. This data structure is used to keep track of the different disjoint sets.
\nIt basically performs two operations :<\/p>\n

    \n
  1. Union :<\/strong> It takes two vertices and join them in a single set (if it is not already there).<\/li>\n
  2. Find :<\/strong> Determines in which subset the element is.<\/li>\n<\/ol>\n

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

    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.<\/p>\n<\/blockquote>\n

    Algorithms :<\/h3>\n

    dfs()<\/strong> :<\/p>\n

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

        union()<\/strong> :<\/p>\n

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

            find()<\/strong> : <\/p>\n

              \n
            1. If (parent[v]==v)<\/code>, returns the vertex v<\/code> (which is root).<\/li>\n
            2. Else, update parent[v]<\/code> by recursively looking up the tree for the root. (find(parent[v]))<\/code>.<\/li>\n<\/ol>\n<\/blockquote>\n

              Complexity Analysis:<\/h3>\n
              \n

              The time complexity<\/strong> of Depth First Search<\/strong> is represented in the form of O(V + E)<\/code>, where V<\/code> is the number of nodes and E<\/code> is the number of edges.<\/p>\n

              The space complexity<\/strong> of the algorithm is O(V)<\/code> as it requires one array ( visited[ ]) of size V<\/code>.<\/p>\n

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

              Solutions:<\/h3>\n

              \t\t\t\t\t\t