{"id":1880,"date":"2020-07-01T09:46:15","date_gmt":"2020-07-01T09:46:15","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1880"},"modified":"2022-03-23T23:28:36","modified_gmt":"2022-03-23T23:28:36","slug":"maximum-edges","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/maximum-edges\/","title":{"rendered":"Maximum Edges"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

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

Difficulty Level<\/h3>\n
\n

Medium<\/p>\n<\/blockquote>\n

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

Given N<\/code> number of vertices, M<\/code> number of edges and relation between them to form an undirected graph, our task is to find the maximum number of edges among all the connected components in the given graph. <\/p>\n<\/blockquote>\n

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

Solution Approach :<\/h3>\n

Introduction :<\/h4>\n
\n

Idea is to traverse the graph and count the edges for every connected component (refer to the connected components article) and print the maximum edge count.<\/p>\n

This can be done using dfs<\/strong> or Disjoint Set<\/strong>.<\/p>\n<\/blockquote>\n

\"\"<\/p>\n

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

We will traverse for every vertex v<\/code> using dfs()<\/strong>, keep track whether it is visited or not using visited[]<\/code> array of boolean type. If v<\/code> is un-visited we will mark it visited (visited[v]=true<\/code>), then traverse for all the adjacent vertices of v<\/code>, for each adjacent vertex a<\/code>, we will increment edge count by 1<\/code> and if a<\/code> is un-visited, recursive call dfs(a<\/code>)<\/strong>. <\/p>\n

Now after the first dfs()<\/strong> call a single connected component has been visited and it will return number of edges of this component, this process will be repeated for all vertices and every time it will return the number of edges of some component. One important thing to notice is that it will return twice the actual edge count (why? refer to Handshaking Lemma<\/strong>), so we need to divide edge count by 2<\/code> to get the actual number of edges. We will store the maximum of all the edge count and print it.<\/p>\n<\/blockquote>\n

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

Although main idea behind the solution approach remains un-changed. We are going to use Disjoint Set Union<\/strong> or DSU<\/strong> data structure as an alternate way to solve our problem. 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
    \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.
    \nWe are using an additional array size[]<\/code> to keep the size of the edges for each root of our set. ith<\/code> index of size[]<\/code> will give us the number of edges in the tree rooted with i<\/code>.
    \nWe will perform union<\/strong> for every edge. After processing all the edges iterate through size[]<\/code> and print the maximum value i.e maximum edge count. <\/li>\n<\/ol>\n<\/blockquote>\n

    Algorithms :<\/h3>\n
    \n

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

      \n
    1. for every vertex 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
      • increment the edge_count by 1<\/code>.<\/li>\n
      • if a<\/code> is not visited i.e visited[a]= false<\/code>, <\/li>\n<\/ul>\n<\/li>\n<\/ol>\n<\/blockquote>\n

        recursively call dfs(a<\/code>)<\/strong>.<\/p>\n

        \n
          \n
        • return edge_count.<\/li>\n<\/ul>\n<\/blockquote>\n

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

          \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]>* else if (<\/code>level[a]>level[b]), update <\/code>parent[b] = a & <\/code>size[a]+=size[b]+1`.<\/li>\n
            • else , update parent[b]=a<\/code>, update level[a] = level[a]+1<\/code> & size[a]+=1<\/code><\/li>\n<\/ul>\n<\/li>\n<\/ol>\n<\/blockquote>\n

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

              \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 the first method is represented in the form of O(V+E)<\/code>, where V<\/code> is the number of verices and E<\/code> is the number of edges.<\/p>\n

                The space complexity<\/strong> of the algorithm is O(V)<\/code> for visited[]<\/code> & colour[]<\/code> array.<\/p>\n<\/blockquote>\n

                Solutions:<\/h3>\n

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