Dado un grafo acíclico dirigido de N Nodes, la tarea es encontrar el conjunto más pequeño de vértices desde el cual se puede visitar el grafo completo.
Ejemplos:
Entrada: Gráfico en la imagen de abajo
Salida: 0 4
Explicación: A partir del vértice 0, el conjunto de Nodes que se pueden visitar es {0 ,1}. Del mismo modo, desde el vértice 4, se puede visitar {4, 3, 2}. Por lo tanto, el gráfico completo se puede visitar desde el conjunto {0, 4} que es del tamaño mínimo posible.Entrada: Gráfico en la imagen de abajo
Salida: 3 4
Enfoque 1: el problema dado se puede resolver utilizando la clasificación topológica para obtener el orden de los vértices de modo que para cada borde dirigido de U a V , U viene antes de V . A continuación se detallan los pasos a seguir:
- Ordene la array dada de vértices en orden topológico utilizando el Algoritmo de Khan .
- Mantenga una array visitada que realice un seguimiento de los vértices visitados.
- Iterar la array ordenada realizar las siguientes operaciones:
- Si no se visita el vértice actual, insértelo en el conjunto requerido.
- Visite todos los Nodes a los que se puede acceder desde el Node insertado mediante DFS transversal.
A continuación se muestra la implementación del enfoque anterior:
Python3
# Python program of the above approach
from collections import defaultdict, deque
class Solution:
# Function to perform DFS
def dfs(self, node, vis, graph):
# add node to visited set
vis.add(node)
for adj in graph[node]:
if (adj not in vis):
self.dfs(adj, vis, graph)
def solve(self, edges):
graph = defaultdict(list)
# dictionary storing
# indegrees of node
indeg = defaultdict(int)
# array to store topological
# sorting of the array
topo_sort = []
vis = set()
for (u, v) in edges:
graph[u].append(v)
# count indegree of each node
indeg[v] += 1
qu = deque()
for u in graph:
# add to ququ ,if indegree
# of node u is 0
if(indeg[u] == 0):
qu.append(u)
# Run till queue is not empty
while(qu):
node = qu.popleft()
# add node to topo_sort
topo_sort.append(node)
# traverse adj nodes
for adj in graph[node]:
# decrement count of indegree
# of each adj node by 1
indeg[adj] -= 1
# if count becomes 0, then
# add adj to qu
if (indeg[adj] == 0):
qu.append(adj)
vis = set()
ans = []
# Take each node from topo_sort
for node in topo_sort:
# check if node is visited
if (node not in vis):
vis.add(node)
ans.append(node)
# Mark all the reachable
# nodes as visited
self.dfs(node, vis, graph)
# finally return ans
return (ans)
obj = Solution()
edges = [[0, 1], [2, 1], [3, 2], [4, 3]]
ans = obj.solve(edges)
print(" ".join(str(n) for n in ans))
Producción
0 4
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Enfoque 2: El problema dado también se puede resolver usando la observación de que los vértices con grado de entrada 0 son los vértices que no se pueden alcanzar desde ningún otro vértice. Por lo tanto, la idea es encontrar el grado de entrada de cada vértice e insertar los vértices con grado de entrada 0 en el conjunto requerido, ya que todos los demás vértices se pueden visitar eventualmente.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find smallest set
// of vertices from which the
// complete graph can be visited
vector<int> solve(vector<vector<int>>& edges)
{
map<int, int> graph;
// Dictionary storing
// indegree of nodes
map<int, int> indeg;
for(auto dt : edges)
{
graph[dt[0]] = dt[1];
// Count indegree of
// each node
indeg[dt[1]] += 1;
}
vector<int> ans;
for(auto it = graph.begin();
it != graph.end(); ++it)
{
// Add to ans, if indegree
// of node u is 0
if (!indeg.count(it->first))
ans.push_back(it->first);
}
// Return Ans
return ans;
}
// Driver code
int main()
{
vector<vector<int>> edges = { { 0, 1 }, { 2, 1 },
{ 3, 2 }, { 4, 3 } };
vector<int> ans = solve(edges);
for(auto dt : ans)
cout << dt << " ";
return 0;
}
// This code is contributed by rakeshsahni
Java
// Java program of the above approach
import java.util.*;
class GFG{
// Function to find smallest set
// of vertices from which the
// complete graph can be visited
static Vector<Integer> solve(int[][] edges)
{
HashMap<Integer,Integer> graph = new HashMap<Integer,Integer>();
// Dictionary storing
// indegree of nodes
HashMap<Integer,Integer> indeg = new HashMap<Integer,Integer>();
for(int dt[] : edges)
{
graph.put(dt[0], dt[1]);
// Count indegree of
// each node
if(indeg.containsKey(dt[1])) {
indeg.put(dt[1], indeg.get(dt[1])+1);
}
else
indeg.put(dt[1], 1);
}
Vector<Integer> ans = new Vector<Integer>();
for (Map.Entry<Integer,Integer> it : graph.entrySet())
{
// Add to ans, if indegree
// of node u is 0
if (!indeg.containsKey(it.getKey()))
ans.add(it.getKey());
}
// Return Ans
return ans;
}
// Driver code
public static void main(String[] args)
{
int[][]edges = { { 0, 1 }, { 2, 1 },
{ 3, 2 }, { 4, 3 } };
Vector<Integer> ans = solve(edges);
for(int dt : ans)
System.out.print(dt+ " ");
}
}
// This code is contributed by shikhasingrajput
Python3
# Python program of the above approach
from collections import defaultdict
class Solution:
# Function to find smallest set
# of vertices from which the
# complete graph can be visited
def solve(self , edges):
graph = defaultdict(list)
# dictionary storing
# indegree of nodes
indeg = defaultdict(int)
for (u,v) in edges:
graph[u].append(v)
# count indegree of
# each node
indeg[v] +=1
ans = []
for u in graph:
# add to ans, if indegree
# of node u is 0
if(indeg[u] == 0):
ans.append(u)
# Return Ans
return (ans)
obj = Solution()
edges = [[0,1] , [2,1] , [3,2] , [4,3] ]
ans= obj.solve(edges)
print(" ".join(str(n) for n in ans))
C#
// C# program of the above approach
using System;
using System.Collections.Generic;
public class GFG {
// Function to find smallest set
// of vertices from which the
// complete graph can be visited
static List<int> solve(int[, ] edges)
{
Dictionary<int, int> graph
= new Dictionary<int, int>();
// Dictionary storing
// indegree of nodes
Dictionary<int, int> indeg
= new Dictionary<int, int>();
for (int k = 0; k < edges.GetLength(0); k++) {
int keys = edges[k, 0];
int values = edges[k, 1];
graph.Add(keys, values);
// Count indegree of
// each node
if (indeg.ContainsKey(values)) {
indeg[values] += 1;
}
else
indeg.Add(values, 1);
}
List<int> ans = new List<int>();
foreach(KeyValuePair<int, int> it in graph)
{
// Add to ans, if indegree
// of node u is 0
if (!indeg.ContainsKey(it.Key))
ans.Add(it.Key);
}
// Return Ans
return ans;
}
public static int[] GetRow(int[, ] matrix, int row)
{
var rowLength = matrix.GetLength(1);
var rowVector = new int[rowLength];
for (var i = 0; i < rowLength; i++)
rowVector[i] = matrix[row, i];
return rowVector;
}
// Driver code
public static void Main(String[] args)
{
int[, ] edges
= { { 0, 1 }, { 2, 1 }, { 3, 2 }, { 4, 3 } };
List<int> ans = solve(edges);
foreach(int dt in ans) Console.Write(dt + " ");
}
}
// This code is contributed by 29AjayKumar
Producción
0 4
Complejidad temporal: O(N)
Espacio auxiliar: O(N)