Hay un total de n tareas que debe elegir, etiquetadas de 0 a n-1. Algunas tareas pueden tener requisitos previos, por ejemplo, para elegir la tarea 0, primero debe elegir la tarea 1, que se expresa como un par: [0, 1]
Dada la cantidad total de tareas y una lista de pares de requisitos previos, ¿es posible para usted? para terminar todas las tareas?
Ejemplos:
Entrada: 2, [[1, 0]]
Salida: verdadero
Explicación: Hay un total de 2 tareas para elegir. Para elegir la tarea 1, debe haber terminado la tarea 0. Entonces es posible.
Entrada: 2, [[1, 0], [0, 1]]
Salida: falso
Explicación: hay un total de 2 tareas para elegir. Para elegir la tarea 1, debe haber terminado la tarea 0, y para elegir la tarea 0, también debe haber terminado la tarea 1. Por lo tanto, es imposible.
Entrada: 3, [[1, 0], [2, 1], [3, 2]]
Salida: verdadero
Explicación: hay un total de 3 tareas para elegir. Para escoger la tarea 1 deberías haber terminado la tarea 0, y para escoger la tarea 2 deberías haber terminado la tarea 1 y para escoger la tarea 3 deberías haber terminado la tarea 2. Así que es posible.
Preguntado en: Google, Twitter, Amazon y muchas empresas más.
Solución: Podemos considerar este problema como un problema gráfico (relacionado con la clasificación topológica ). Todas las tareas son Nodes del gráfico y si la tarea u es un requisito previo de la tarea v, agregaremos un borde dirigido desde el Node u al Node v. Ahora, este problema es equivalente a detectar un ciclo en el gráfico representado por requisitos previos. Si hay un ciclo en el gráfico, entonces no es posible terminar todas las tareas (porque en ese caso no hay ningún orden topológico de tareas). Tanto BFS como DFS se pueden usar para resolverlo.
Dado que el par es un inconveniente para la implementación de algoritmos gráficos, primero lo transformamos en un gráfico. Si la tarea u es un requisito previo de la tarea v, agregaremos un borde dirigido desde el Node u al Node v.
Requisito previo: Detectar ciclo en un gráfico dirigido
usandoDFS Para DFS, primero visitará un Node, luego un vecino del mismo, luego un vecino de este vecino… y así sucesivamente. Si se encuentra con un Node que fue visitado en el proceso actual de visita DFS, se detecta un ciclo y devolveremos falso. De lo contrario, comenzará desde otro Node no visitado y repetirá este proceso hasta que se hayan visitado todos los Nodes. Tenga en cuenta que debe realizar dos registros: uno es para registrar todos los Nodes visitados y el otro es para registrar los Nodes visitados en la visita DFS actual.
El código es el siguiente. Usamos un vector visitado para registrar todos los Nodes visitados y otro vector onpath para registrar los Nodes visitados de la visita DFS actual. Una vez finalizada la visita actual, restablecemos el valor onpath del Node inicial a falso.
CPP
// CPP program to check whether we can finish all
// tasks or not from given dependencies.
#include <bits/stdc++.h>
using namespace std;
// Returns adjacency list representation from a list
// of pairs.
vector<unordered_set<int> > make_graph(int numTasks,
vector<pair<int, int> >& prerequisites)
{
vector<unordered_set<int> > graph(numTasks);
for (auto pre : prerequisites)
graph[pre.second].insert(pre.first);
return graph;
}
// A DFS based function to check if there is a cycle
// in the directed graph.
bool dfs_cycle(vector<unordered_set<int> >& graph, int node,
vector<bool>& onpath, vector<bool>& visited)
{
if (visited[node])
return false;
onpath[node] = visited[node] = true;
for (int neigh : graph[node])
if (onpath[neigh] || dfs_cycle(graph, neigh, onpath, visited))
return true;
return onpath[node] = false;
}
// Main function to check whether possible to finish all tasks or not
bool canFinish(int numTasks, vector<pair<int, int> >& prerequisites)
{
vector<unordered_set<int> > graph = make_graph(numTasks, prerequisites);
vector<bool> onpath(numTasks, false), visited(numTasks, false);
for (int i = 0; i < numTasks; i++)
if (!visited[i] && dfs_cycle(graph, i, onpath, visited))
return false;
return true;
}
int main()
{
int numTasks = 4;
vector<pair<int, int> > prerequisites;
// for prerequisites: [[1, 0], [2, 1], [3, 2]]
prerequisites.push_back(make_pair(1, 0));
prerequisites.push_back(make_pair(2, 1));
prerequisites.push_back(make_pair(3, 2));
if (canFinish(numTasks, prerequisites)) {
cout << "Possible to finish all tasks";
}
else {
cout << "Impossible to finish all tasks";
}
return 0;
}
Java
// Java program to check whether we can finish all
// tasks or not from given dependencies.
import java.util.*;
public class GFG{
// class to store dependencies as a pair
static class pair{
int first, second;
pair(int first, int second){
this.first = first;
this.second = second;
}
}
// Returns adjacency list representation from a list
// of pairs.
static ArrayList<ArrayList<Integer>> make_graph(int numTasks,
Vector<pair> prerequisites)
{
ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>(numTasks);
for(int i=0; i<numTasks; i++){
graph.add(new ArrayList<Integer>());
}
for (pair pre : prerequisites)
graph.get(pre.second).add(pre.first);
return graph;
}
// A DFS based function to check if there is a cycle
// in the directed graph.
static boolean dfs_cycle(ArrayList<ArrayList<Integer>> graph, int node,
boolean onpath[], boolean visited[])
{
if (visited[node])
return false;
onpath[node] = visited[node] = true;
for (int neigh : graph.get(node))
if (onpath[neigh] || dfs_cycle(graph, neigh, onpath, visited))
return true;
return onpath[node] = false;
}
// Main function to check whether possible to finish all tasks or not
static boolean canFinish(int numTasks, Vector<pair> prerequisites)
{
ArrayList<ArrayList<Integer>> graph = make_graph(numTasks, prerequisites);
boolean onpath[] = new boolean[numTasks];
boolean visited[] = new boolean[numTasks];
for (int i = 0; i < numTasks; i++)
if (!visited[i] && dfs_cycle(graph, i, onpath, visited))
return false;
return true;
}
public static void main(String args[])
{
int numTasks = 4;
Vector<pair> prerequisites = new Vector<pair>();;
// for prerequisites: [[1, 0], [2, 1], [3, 2]]
prerequisites.add(new pair(1, 0));
prerequisites.add(new pair(2, 1));
prerequisites.add(new pair(3, 2));
if (canFinish(numTasks, prerequisites)) {
System.out.println("Possible to finish all tasks");
}
else {
System.out.println("Impossible to finish all tasks");
}
}
}
// This code is contributed by adityapande88.
Python3
# Python3 program to check whether we can finish all
# tasks or not from given dependencies.
# class to store dependencies as a pair
class pair:
def __init__(self, first, second):
self.first = first
self.second = second
# Returns adjacency list representation from a list
# of pairs.
def make_graph(numTasks, prerequisites):
graph = []
for i in range(numTasks):
graph.append([])
for pre in prerequisites:
graph[pre.second].append(pre.first)
return graph
# A DFS based function to check if there is a cycle
# in the directed graph.
def dfs_cycle(graph, node, onpath, visited):
if visited[node]:
return false
onpath[node] = visited[node] = True
for neigh in graph[node]:
if (onpath[neigh] or dfs_cycle(graph, neigh, onpath, visited)):
return true
return False
# Main function to check whether possible to finish all
# tasks or not
def canFinish(numTasks, prerequisites):
graph = make_graph(numTasks, prerequisites)
onpath = [False]*numTasks
visited = [False]*numTasks
for i in range(numTasks):
if (not visited[i] and dfs_cycle(graph, i, onpath, visited)):
return False
return True
# Driver code to test above functions
numTasks = 4
prerequisites = []
prerequisites.append(pair(1, 0))
prerequisites.append(pair(2, 1))
prerequisites.append(pair(3, 2))
if canFinish(numTasks, prerequisites):
print("Possible to finish all tasks")
else:
print("Impossible to finish all tasks")
# This code is contributed by Abhijeet Kumar(abhijeet19403)
C#
// C# program to check whether we can finish all
// tasks or not from given dependencies.
using System;
using System.Collections.Generic;
public class GFG {
// class to store dependencies as a pair
public class pair {
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Returns adjacency list representation from a list
// of pairs.
static List<List<int> >
make_graph(int numTasks, List<pair> prerequisites)
{
List<List<int> > graph
= new List<List<int> >(numTasks);
for (int i = 0; i < numTasks; i++) {
graph.Add(new List<int>());
}
foreach(pair pre in prerequisites) graph[pre.second]
.Add(pre.first);
return graph;
}
// A DFS based function to check if there is a cycle
// in the directed graph.
static bool dfs_cycle(List<List<int> > graph, int node,
bool[] onpath, bool[] visited)
{
if (visited[node])
return false;
onpath[node] = visited[node] = true;
foreach( int neigh in graph[node])
if (onpath[neigh] || dfs_cycle(graph, neigh, onpath,
visited))
return true;
//onpath[node] = false;
return false;
}
// Main function to check whether possible to finish all
// tasks or not
static bool canFinish(int numTasks,
List<pair> prerequisites)
{
List<List<int> > graph
= make_graph(numTasks, prerequisites);
bool[] onpath = new bool[numTasks];
bool[] visited = new bool[numTasks];
for (int i = 0; i < numTasks; i++)
if (!visited[i]
&& dfs_cycle(graph, i, onpath, visited))
return false;
return true;
}
public static void Main(String[] args)
{
int numTasks = 4;
List<pair> prerequisites = new List<pair>();
;
// for prerequisites: [[1, 0], [2, 1], [3, 2]]
prerequisites.Add(new pair(1, 0));
prerequisites.Add(new pair(2, 1));
prerequisites.Add(new pair(3, 2));
if (canFinish(numTasks, prerequisites)) {
Console.WriteLine(
"Possible to finish all tasks");
}
else {
Console.WriteLine(
"Impossible to finish all tasks");
}
}
}
// This code is contributed by Abhijeet Kumar(abhijeet19403)
Possible to finish all tasks
Usando BFS
BFS se puede usar para resolverlo usando la idea de clasificación topológica. Si la clasificación topológica es posible, significa que no hay ciclo y es posible terminar todas las tareas.
BFS usa los grados de entrada de cada Node. Primero intentaremos encontrar un Node con 0 grados. Si no lo hacemos, debe haber un ciclo en el gráfico y devolvemos falso. De lo contrario, hemos encontrado uno. Establecemos su grado de entrada en -1 para evitar volver a visitarlo y reducir los grados de entrada de todos sus vecinos en 1. Este proceso se repetirá n (número de Nodes) veces. Si no hemos devuelto falso, devolveremos verdadero.
CPP
// A BFS based solution to check if we can finish
// all tasks or not. This solution is mainly based
// on Kahn's algorithm.
#include <bits/stdc++.h>
using namespace std;
// Returns adjacency list representation from a list
// of pairs.
vector<unordered_set<int> >
make_graph(int numTasks,
vector<pair<int, int> >& prerequisites)
{
vector<unordered_set<int> > graph(numTasks);
for (auto pre : prerequisites)
graph[pre.second].insert(pre.first);
return graph;
}
// Finds in-degree of every vertex
vector<int>
compute_indegree(vector<unordered_set<int> >& graph)
{
vector<int> degrees(graph.size(), 0);
for (auto neighbors : graph)
for (int neigh : neighbors)
degrees[neigh]++;
return degrees;
}
// Main function to check whether possible to finish all
// tasks or not
bool canFinish(int numTasks,
vector<pair<int, int> >& prerequisites)
{
vector<unordered_set<int> > graph
= make_graph(numTasks, prerequisites);
vector<int> degrees = compute_indegree(graph);
for (int i = 0; i < numTasks; i++) {
int j = 0;
for (; j < numTasks; j++)
if (!degrees[j])
break;
if (j == numTasks)
return false;
degrees[j] = -1;
for (int neigh : graph[j])
degrees[neigh]--;
}
return true;
}
int main()
{
int numTasks = 4;
vector<pair<int, int> > prerequisites;
prerequisites.push_back(make_pair(1, 0));
prerequisites.push_back(make_pair(2, 1));
prerequisites.push_back(make_pair(3, 2));
if (canFinish(numTasks, prerequisites)) {
cout << "Possible to finish all tasks";
}
else {
cout << "Impossible to finish all tasks";
}
return 0;
}
Java
// A BFS based solution to check if we can finish
// all tasks or not. This solution is mainly based
// on Kahn's algorithm.
import java.util.*;
public class GFG {
// class to store dependencies as a pair
static class pair {
int first, second;
pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Returns adjacency list representation from a list
// of pairs.
static ArrayList<ArrayList<Integer> >
make_graph(int numTasks, Vector<pair> prerequisites)
{
ArrayList<ArrayList<Integer> > graph
= new ArrayList<ArrayList<Integer> >(numTasks);
for (int i = 0; i < numTasks; i++) {
graph.add(new ArrayList<Integer>());
}
for (pair pre : prerequisites)
graph.get(pre.second).add(pre.first);
return graph;
}
// Finds in-degree of every vertex
static int[] compute_indegree(
ArrayList<ArrayList<Integer> > graph)
{
int degrees[] = new int[graph.size()];
for (ArrayList<Integer> neighbors : graph)
for (int neigh : neighbors)
degrees[neigh]++;
return degrees;
}
// Main function to check whether possible to finish all
// tasks or not
static boolean canFinish(int numTasks,
Vector<pair> prerequisites)
{
ArrayList<ArrayList<Integer> > graph
= make_graph(numTasks, prerequisites);
int degrees[] = compute_indegree(graph);
for (int i = 0; i < numTasks; i++) {
int j = 0;
for (; j < numTasks; j++)
if (degrees[j] == 0)
break;
if (j == numTasks)
return false;
degrees[j] = -1;
for (int neigh : graph.get(j))
degrees[neigh]--;
}
return true;
}
public static void main(String args[])
{
int numTasks = 4;
Vector<pair> prerequisites = new Vector<pair>();
prerequisites.add(new pair(1, 0));
prerequisites.add(new pair(2, 1));
prerequisites.add(new pair(3, 2));
if (canFinish(numTasks, prerequisites)) {
System.out.println(
"Possible to finish all tasks");
}
else {
System.out.println(
"Impossible to finish all tasks");
}
}
}
// This code is contributed by adityapande88.
Python3
# A BFS based solution to check if we can finish
# all tasks or not. This solution is mainly based
# on Kahn's algorithm.
# class to store dependencies as a pair
class pair:
def __init__(self, first, second):
self.first = first
self.second = second
# Returns adjacency list representation from a list
# of pairs.
def make_graph(numTasks, prerequisites):
graph = []
for i in range(numTasks):
graph.append([])
for pre in prerequisites:
graph[pre.second].append(pre.first)
return graph
# Finds in-degree of every vertex
def compute_indegree(graph):
degrees = [0]*len(graph)
for neighbors in graph:
for neigh in neighbors:
degrees[neigh] += 1
return degrees
# Main function to check whether possible to finish all tasks or not
def canFinish(numTasks, prerequisites):
graph = make_graph(numTasks, prerequisites)
degrees = compute_indegree(graph)
for i in range(numTasks):
j = 0
while(j < numTasks):
if (degrees[j] == 0):
break
j += 1
if (j == numTasks):
return False
degrees[j] = -1
for neigh in graph[j]:
degrees[neigh] -= 1
return True
numTasks = 4
prerequisites = []
prerequisites.append(pair(1, 0))
prerequisites.append(pair(2, 1))
prerequisites.append(pair(3, 2))
if (canFinish(numTasks, prerequisites)):
print("Possible to finish all tasks")
else:
print("Impossible to finish all tasks")
# This code is contributed by Lovely Jain
C#
// A BFS based solution to check if we can finish
// all tasks or not. This solution is mainly based
// on Kahn's algorithm.
using System;
using System.Collections.Generic;
public class GFG {
// class to store dependencies as a pair
public class pair {
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Returns adjacency list representation from a list
// of pairs.
static List<List<int> >
make_graph(int numTasks, List<pair> prerequisites)
{
List<List<int> > graph
= new List<List<int> >(numTasks);
for (int i = 0; i < numTasks; i++) {
graph.Add(new List<int>());
}
foreach(pair pre in prerequisites)
graph[pre.second].Add(pre.first);
return graph;
}
// Finds in-degree of every vertex
static int[] compute_indegree(
List<List<int> > graph)
{
int[] degrees = new int[graph.Count];
foreach(List<int> neighbors in graph)
foreach(int neigh in neighbors)
degrees[neigh]++;
return degrees;
}
// Main function to check whether possible to finish all
// tasks or not
static bool canFinish(int numTasks,
List<pair> prerequisites)
{
List<List<int> > graph
= make_graph(numTasks, prerequisites);
int[] degrees = compute_indegree(graph);
for (int i = 0; i < numTasks; i++) {
int j = 0;
for (; j < numTasks; j++)
if (degrees[j] == 0)
break;
if (j == numTasks)
return false;
degrees[j] = -1;
foreach(int neigh in graph[j])
degrees[neigh]--;
}
return true;
}
public static void Main(String[] args)
{
int numTasks = 4;
List<pair> prerequisites = new List<pair>();
prerequisites.Add(new pair(1, 0));
prerequisites.Add(new pair(2, 1));
prerequisites.Add(new pair(3, 2));
if (canFinish(numTasks, prerequisites)) {
Console.WriteLine(
"Possible to finish all tasks");
}
else {
Console.WriteLine(
"Impossible to finish all tasks");
}
}
}
// This code is contributed by Abhijeet Kumar(abhijeet19403)
Possible to finish all tasks
Referencia:
https://leetcode.com/problems/course-schedule/
Publicación traducida automáticamente
Artículo escrito por shashipk11 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA