Depth First Search, Disjoint Set
Problem Statement :
Nnumber of vertices,
Mnumber 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.
Solution Approach :
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 dfs or Disjoint Set.
Method 1 (Using DFS) :
We will traverse for every vertex
vusing dfs(), keep track whether it is visited or not using
visitedarray of boolean type. If
vis 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
ais un-visited, recursive call dfs(
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 to Handshaking Lemma), so we need to divide edge count by
2to 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 Union or DSU data structure as an alternate way to solve our problem. 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 :
- 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
sizeto keep the size of the edges for each root of our set.
sizewill give us the number of edges in the tree rooted with
We will perform union for every edge. After processing all the edges iterate through
sizeand print the maximum value i.e maximum edge count.
- for every vertex
v, we will mark the vertex
vas visited (
- Iterate for all the adjacent vertices of
vand for every adjacent vertex
a, do following :
- increment the edge_count by
ais not visited i.e
recursively call dfs(
- return edge_count.
- For two vertices
v, find the root for both vertices using find() (
b = find(v)).
- If the root of
vare not similar, check the level of
- if (
level[a]>* else if (level[a]>level[b]
), updateparent[b] = a
- else , update
level[a] = level[a]+1&
(parent[v]==v), returns the vertex
v(which is root).
- Else, update
parent[v]by recursively looking up the tree for the root.
The time complexity of the first method is represented in the form of
Vis the number of verices and
Eis the number of edges.
The space complexity of the algorithm is