Dado un grafo acíclico no dirigido que tiene N Nodes y M aristas, la tarea es encontrar el tamaño del árbol más grande del bosque formado por el grafo.
Un bosque es una colección de árboles disjuntos. En otras palabras, también podemos decir que forest es una colección de un gráfico acíclico que no está conectado.
Ejemplos:
Entrada: N = 5, bordes[][] = {{0, 1}, {0, 2}, {3, 4}}
Salida: 3
Explicación:
Hay 2 árboles, cada uno con tamaño 3 y 2 respectivamente.0 / \ 1 2y
3 \ 4Por lo tanto, el tamaño del árbol más grande es 3.
Entrada: N = 5, bordes[][] = {{0, 1}, {0, 2}, {3, 4}, {0, 4}, {3, 5}}
Salida: 6
Enfoque: la idea es contar primero el número de Nodes accesibles desde cada bosque. Por lo tanto:
- Aplique DFS en cada Node y obtenga el tamaño del árbol formado por este Node y verifique si cada Node conectado es visitado desde una fuente.
- Si el tamaño del árbol actual es mayor que la respuesta, actualice la respuesta al tamaño del árbol actual.
- Vuelva a realizar el recorrido DFS si aún no se ha visitado algún conjunto de Nodes.
- Finalmente, el máximo de todas las respuestas cuando se visitan todos los Nodes es la respuesta final.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
3
Complejidad temporal: O(V + E) , donde V es el número de vértices y E es el número de aristas.
Publicación traducida automáticamente
Artículo escrito por muskan_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA