#### Concepts Used

Depth First Search, Disjoint Set

#### Difficulty Level

Medium

#### Problem Statement :

Given

`N`

number of vertices,`M`

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.

**See original problem statement here**

#### Solution Approach :

## Introduction :

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.

This can be done using

dfsorDisjoint Set.

## Method 1 (Using DFS) :

We will traverse for every vertex

`v`

usingdfs(), keep track whether it is visited or not using`visited[]`

array of boolean type. If`v`

is un-visited we will mark it visited (`visited[v]=true`

), then traverse for all the adjacent vertices of`v`

, for each adjacent vertex`a`

, we will increment edge count by`1`

and if`a`

is un-visited, recursive calldfs(.`a`

)Now after the first

dfs()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 toHandshaking Lemma), so we need to divide edge count by`2`

to get the actual number of edges. We will store the maximum of all the edge count and print it.## Method 2 (Using Disjoint Set):

Although main idea behind the solution approach remains un-changed. visit some best sites to learn coding and use

Disjoint Set UnionorDSUdata structure as an alternate way to solve our problem.DSUdata structure is also sometimes calledUnion-Find Set. This data structure is used to keep track of the different disjoint sets.

It basically performs two operations :

Union :It takes two vertices and join them in a single set (if it is not already there).Find :Determines in which subset the element is.We are using an additional array

`size[]`

to keep the size of the edges for each root of our set.`ith`

index of`size[]`

will give us the number of edges in the tree rooted with`i`

.

We will performunionfor every edge. After processing all the edges iterate through`size[]`

and print the maximum value i.e maximum edge count.## Algorithms :

dfs():

- for every vertex
`v`

, we will mark the vertex`v`

as visited (`visited[v]= true`

).- Iterate for all the adjacent vertices of
`v`

and for every adjacent vertex`a`

, do following :

- increment the edge_count by
`1`

.- if
`a`

is not visited i.e`visited[a]= false`

,

recursively calldfs(.`a`

)- return edge_count.

union():

- For two vertices
`u`

&`v`

, find the root for both vertices usingfind()(`a=find(u)`

&`b = find(v)`

).- If the root of
`u`

&`v`

are not similar, check the level of`a`

&`b`

as follows:

- if (
`level[a]>* else if (`

level[a]>level[b]`), update`

parent[b] = a`&`

size[a]+=size[b]+1`.- else , update
`parent[b]=a`

, update`level[a] = level[a]+1`

&`size[a]+=1`

find():

- If
`(parent[v]==v)`

, returns the vertex`v`

(which is root).- Else, update
`parent[v]`

by recursively looking up the tree for the root.`(find(parent[v]))`

.

Complexity Analysis:The

time complexityof the first method is represented in the form of`O(V+E)`

, where`V`

is the number of verices and`E`

is the number of edges.The

space complexityof the algorithm is`O(V)`

for`visited[]`

&`colour[]`

array.

## Solutions:

[TABS_R id=1902]

[forminator_quiz id=”1944″]