Size of the Largest Trees in a Forest formed by the given Graph
Given an undirected acyclic graph having N nodes and M edges, the task is to find the size of the largest tree in the forest formed by the graph.
A forest is a collection of disjoint trees. In other words, we can also say that forest is a collection of an acyclic graph which is not connected.
Examples:
Input: N = 5, edges[][] = {{0, 1}, {0, 2}, {3, 4}}
Output: 3
Explanation:
There are 2 trees, each having size 3 and 2 respectively.0 / \ 1 2and
3 \ 4Hence the size of the largest tree is 3.
Input: N = 5, edges[][] = {{0, 1}, {0, 2}, {3, 4}, {0, 4}, {3, 5}}
Output: 6
Approach: The idea is to first count the number of reachable nodes from every forest. Therefore:
- Apply DFS on every node and obtain the size of the tree formed by this node and check if every connected node is visited from one source.
- If the size of the current tree is greater than the answer then update the answer to the current tree’s size.
- Again perform DFS traversal if some set of nodes are not yet visited.
- Finally, the max of all the answers when all the nodes are visited is the final answer.
Below is the implementation of the above approach:
C++
// C++ program to find the size // of the largest tree in the forest #include <bits/stdc++.h> using namespace std; // A utility function to add // an edge in an undirected graph. void addEdge(vector< int > adj[], int u, int v) { adj[u].push_back(v); adj[v].push_back(u); } // A utility function to perform DFS of a // graph recursively from a given vertex u // and returns the size of the tree formed by u int DFSUtil( int u, vector< int > adj[], vector< bool >& visited) { visited[u] = true ; int sz = 1; // Iterating through all the nodes for ( int i = 0; i < adj[u].size(); i++) if (visited[adj[u][i]] == false ) // Perform DFS if the node is // not yet visited sz += DFSUtil( adj[u][i], adj, visited); return sz; } // Function to return the size of the // largest tree in the forest given as // the adjacency list int largestTree(vector< int > adj[], int V) { vector< bool > visited(V, false ); int answer = 0; // Iterating through all the vertices for ( int u = 0; u < V; u++) { if (visited[u] == false ) { // Find the answer answer = max(answer, DFSUtil(u, adj, visited)); } } return answer; } // Driver code int main() { int V = 5; vector< int > adj[V]; addEdge(adj, 0, 1); addEdge(adj, 0, 2); addEdge(adj, 3, 4); cout << largestTree(adj, V); return 0; } |
Java
// Java program to find the size // of the largest tree in the forest import java.util.*; class GFG{ // A utility function to add // an edge in an undirected graph. static void addEdge(Vector<Integer> adj[], int u, int v) { adj[u].add(v); adj[v].add(u); } // A utility function to perform DFS of a // graph recursively from a given vertex u // and returns the size of the tree formed by u static int DFSUtil( int u, Vector<Integer> adj[], Vector<Boolean> visited) { visited.add(u, true ); int sz = 1 ; // Iterating through all the nodes for ( int i = 0 ; i < adj[u].size(); i++) if (visited.get(adj[u].get(i)) == false ) // Perform DFS if the node is // not yet visited sz += DFSUtil(adj[u].get(i), adj, visited); return sz; } // Function to return the size of the // largest tree in the forest given as // the adjacency list static int largestTree(Vector<Integer> adj[], int V) { Vector<Boolean> visited = new Vector<>(); for ( int i = 0 ; i < V; i++) { visited.add( false ); } int answer = 0 ; // Iterating through all the vertices for ( int u = 0 ; u < V; u++) { if (visited.get(u) == false ) { // Find the answer answer = Math.max(answer, DFSUtil(u, adj, visited)); } } return answer; } // Driver code public static void main(String[] args) { int V = 5 ; Vector<Integer> adj[] = new Vector[V]; for ( int i = 0 ; i < adj.length; i++) adj[i] = new Vector<Integer>(); addEdge(adj, 0 , 1 ); addEdge(adj, 0 , 2 ); addEdge(adj, 3 , 4 ); System.out.print(largestTree(adj, V)); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program to find the size # of the largest tree in the forest # A utility function to add # an edge in an undirected graph. def addEdge(adj, u, v): adj[u].append(v) adj[v].append(u) # A utility function to perform DFS of a # graph recursively from a given vertex u # and returns the size of the tree formed by u def DFSUtil(u, adj, visited): visited[u] = True sz = 1 # Iterating through all the nodes for i in range ( 0 , len (adj[u])): if (visited[adj[u][i]] = = False ): # Perform DFS if the node is # not yet visited sz + = DFSUtil(adj[u][i], adj, visited) return sz # Function to return the size of the # largest tree in the forest given as # the adjacency list def largestTree(adj, V): visited = [ False for i in range (V)] answer = 0 # Iterating through all the vertices for u in range (V): if (visited[u] = = False ): # Find the answer answer = max (answer,DFSUtil( u, adj, visited)) return answer # Driver code if __name__ = = "__main__" : V = 5 adj = [[] for i in range (V)] addEdge(adj, 0 , 1 ) addEdge(adj, 0 , 2 ) addEdge(adj, 3 , 4 ) print (largestTree(adj, V)) # This code is contributed by rutvik_56 |
C#
// C# program to find the size // of the largest tree in the forest using System; using System.Collections.Generic; class GFG{ // A utility function to add // an edge in an undirected graph. static void addEdge(List< int > []adj, int u, int v) { adj[u].Add(v); adj[v].Add(u); } // A utility function to perform DFS of a // graph recursively from a given vertex u // and returns the size of the tree formed by u static int DFSUtil( int u, List< int > []adj, List<Boolean> visited) { visited.Insert(u, true ); int sz = 1; // Iterating through all the nodes for ( int i = 0; i < adj[u].Count; i++) if (visited[adj[u][i]] == false ) // Perform DFS if the node is // not yet visited sz += DFSUtil(adj[u][i], adj, visited); return sz; } // Function to return the size of the // largest tree in the forest given as // the adjacency list static int largestTree(List< int > []adj, int V) { List<Boolean> visited = new List<Boolean>(); for ( int i = 0; i < V; i++) { visited.Add( false ); } int answer = 0; // Iterating through all the vertices for ( int u = 0; u < V; u++) { if (visited[u] == false ) { // Find the answer answer = Math.Max(answer, DFSUtil(u, adj, visited)); } } return answer; } // Driver code public static void Main(String[] args) { int V = 5; List< int > []adj = new List< int >[V]; for ( int i = 0; i < adj.Length; i++) adj[i] = new List< int >(); addEdge(adj, 0, 1); addEdge(adj, 0, 2); addEdge(adj, 3, 4); Console.Write(largestTree(adj, V)); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript program to find the size // of the largest tree in the forest // A utility function to add // an edge in an undirected graph. function addEdge(adj, u, v) { adj[u].push(v); adj[v].push(u); } // A utility function to perform DFS of a // graph recursively from a given vertex u // and returns the size of the tree formed by u function DFSUtil(u, adj, visited) { visited[u] = true ; let sz = 1; // Iterating through all the nodes for (let i = 0; i < adj[u].length; i++) { if (visited[adj[u][i]] == false ) { // Perform DFS if the node is // not yet visited sz += DFSUtil(adj[u][i], adj, visited); } } return sz; } // Function to return the size of the // largest tree in the forest given as // the adjacency list function largestTree(adj, V) { let visited = new Array(V); visited.fill( false ); let answer = 0; // Iterating through all the vertices for (let u = 0; u < V; u++) { if (visited[u] == false ) { // Find the answer answer = Math.max(answer,DFSUtil(u, adj, visited)); } } return answer; } let V = 5; let adj = []; for (let i = 0; i < V; i++) { adj.push([]); } addEdge(adj, 0, 1); addEdge(adj, 0, 2); addEdge(adj, 3, 4); document.write(largestTree(adj, V)); // This code is contributed by divyesh072019. </script> |
3
Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges.