Hay un total de n tareas que debe elegir, etiquetadas de 0 a n-1. Algunas tareas pueden tener tareas de requisitos previos, por ejemplo, para elegir la tarea 0, primero debe terminar 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, devuelva el orden de tareas que debe elegir para terminar todas las tareas. Puede haber varios pedidos correctos, solo necesita devolver uno de ellos. Si es imposible terminar todas las tareas, devuelva una array vacía. Ejemplos:
Entrada: 2, [[1, 0]] Salida: [0, 1] Explicación: Hay un total de 2 tareas para elegir. Para elegir la tarea 1, debe haber terminado la tarea 0. Por lo tanto, el orden correcto de las tareas es [0, 1] . Entrada: 4, [[1, 0], [2, 0], [3, 1], [3, 2]] Salida: [0, 1, 2, 3] o [0, 2, 1, 3] Explicación: Hay un total de 4 tareas para elegir. Para elegir la tarea 3, debe haber terminado las tareas 1 y 2. Las tareas 1 y 2 deben elegirse después de terminar la tarea 0. Por lo tanto, un orden de tareas correcto es [0, 1, 2, 3]. Otro orden correcto es [0, 2, 1, 3].
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 encontrar una ordenación topológica de Nodes/tareas (usando clasificación topológica ) 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 la clasificación topológicapara 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. Clasificación topológica usando BFS Aquí usamos el algoritmo de Kahn para la clasificación topológica . 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.
CPP
// CPP program to find order to process tasks
// so that all tasks can be finished. This program
// mainly uses Kahn's algorithm.
#include <bits/stdc++.h>
using namespace std;
// Returns adjacency list representation of graph from
// given set 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;
}
// Computes 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 for topological sorting
vector<int> findOrder(int numTasks,
vector<pair<int, int> >& prerequisites)
{
// Create an adjacency list
vector<unordered_set<int> > graph =
make_graph(numTasks, prerequisites);
// Find vertices of zero degree
vector<int> degrees = compute_indegree(graph);
queue<int> zeros;
for (int i = 0; i < numTasks; i++)
if (!degrees[i])
zeros.push(i);
// Find vertices in topological order
// starting with vertices of 0 degree
// and reducing degrees of adjacent.
vector<int> toposort;
for (int i = 0; i < numTasks; i++) {
if (zeros.empty())
return {};
int zero = zeros.front();
zeros.pop();
toposort.push_back(zero);
for (int neigh : graph[zero]) {
if (!--degrees[neigh])
zeros.push(neigh);
}
}
return toposort;
}
// Driver code
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));
vector<int> v = findOrder(numTasks, prerequisites);
for (int i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
return 0;
}
Java
// Java program to find order to process tasks
// so that all tasks can be finished. This program
// mainly uses Kahn's algorithm.
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
public class Dep {
// Returns adjacency list representation of graph from
// given set of pairs.
static ArrayList<HashSet<Integer> >
make_graph(int numTasks, int[][] prerequisites)
{
ArrayList<HashSet<Integer> > graph
= new ArrayList<HashSet<Integer>>(numTasks);
for (int i = 0; i < numTasks; i++)
graph.add(new HashSet<Integer>());
for (int[] pre : prerequisites)
graph.get(pre[1]).add(pre[0]);
return graph;
}
// Computes in-degree of every vertex
static int[] compute_indegree(
ArrayList<HashSet<Integer> > graph)
{
int[] degrees = new int[graph.size()];
for (HashSet<Integer> neighbors : graph)
for (int neigh : neighbors)
degrees[neigh]++;
return degrees;
}
// main function for topological sorting
static ArrayList<Integer>
findOrder(int numTasks, int[][] prerequisites)
{
// Create an adjacency list
ArrayList<HashSet<Integer> > graph
= make_graph(numTasks, prerequisites);
// Find vertices of zero degree
int[] degrees = compute_indegree(graph);
Queue<Integer> zeros = new LinkedList<Integer>();
for (int i = 0; i < numTasks; i++)
if (degrees[i] == 0)
zeros.add(i);
// Find vertices in topological order
// starting with vertices of 0 degree
// and reducing degrees of adjacent.
ArrayList<Integer> toposort
= new ArrayList<Integer>();
for (int i = 0; i < numTasks; i++) {
if (zeros.isEmpty())
return new ArrayList<Integer>();
int zero = zeros.peek();
zeros.poll();
toposort.add(zero);
for (int neigh : graph.get(zero)) {
if (--degrees[neigh] == 0)
zeros.add(neigh);
}
}
return toposort;
}
// Driver code
public static void main(String[] args)
{
int numTasks = 4;
int[][] prerequisites
= { { 1, 0 }, { 2, 1 }, { 3, 2 } };
ArrayList<Integer> v
= findOrder(numTasks, prerequisites);
for (int i = 0; i < v.size(); i++) {
System.out.print(v.get(i) + " ");
}
}
}
// This code is contributed by Lovely Jain
0 1 2 3
Clasificación topológica usando DFS: en esta implementación, usamos un algoritmo basado en DFS para la clasificación topológica .
CPP
// CPP program to find Topological sorting using
// DFS
#include <bits/stdc++.h>
using namespace std;
// Returns adjacency list representation of graph from
// given set 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;
}
// Does DFS and adds nodes to Topological Sort
bool dfs(vector<unordered_set<int> >& graph, int node,
vector<bool>& onpath, vector<bool>& visited,
vector<int>& toposort)
{
if (visited[node])
return false;
onpath[node] = visited[node] = true;
for (int neigh : graph[node])
if (onpath[neigh] || dfs(graph, neigh, onpath, visited, toposort))
return true;
toposort.push_back(node);
return onpath[node] = false;
}
// Returns an order of tasks so that all tasks can be
// finished.
vector<int> findOrder(int numTasks, vector<pair<int, int> >& prerequisites)
{
vector<unordered_set<int> > graph = make_graph(numTasks, prerequisites);
vector<int> toposort;
vector<bool> onpath(numTasks, false), visited(numTasks, false);
for (int i = 0; i < numTasks; i++)
if (!visited[i] && dfs(graph, i, onpath, visited, toposort))
return {};
reverse(toposort.begin(), toposort.end());
return toposort;
}
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));
vector<int> v = findOrder(numTasks, prerequisites);
for (int i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
return 0;
}
Java
// Java program to find Topological sorting using
// DFS
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
public class Dfs1 {
// Returns adjacency list representation of graph from
// given set of pairs.
static ArrayList<HashSet<Integer> >
make_graph(int numTasks, int[][] prerequisites)
{
ArrayList<HashSet<Integer> > graph
= new ArrayList(numTasks);
for (int i = 0; i < numTasks; i++)
graph.add(new HashSet<Integer>());
for (int[] pre : prerequisites)
graph.get(pre[1]).add(pre[0]);
return graph;
}
// Does DFS and adds nodes to Topological Sort
static boolean dfs(ArrayList<HashSet<Integer> > graph,
int node, boolean[] onpath,
boolean[] visited,
ArrayList<Integer> toposort)
{
if (visited[node])
return false;
onpath[node] = visited[node] = true;
for (int neigh : graph.get(node))
if (onpath[neigh]
|| dfs(graph, neigh, onpath, visited,
toposort))
return true;
toposort.add(node);
return onpath[node] = false;
}
// Returns an order of tasks so that all tasks can be
// finished.
static ArrayList<Integer>
findOrder(int numTasks, int[][] prerequisites)
{
ArrayList<HashSet<Integer> > graph
= make_graph(numTasks, prerequisites);
ArrayList<Integer> toposort
= new ArrayList<Integer>();
boolean[] onpath = new boolean[numTasks];
boolean[] visited = new boolean[numTasks];
for (int i = 0; i < numTasks; i++)
if (!visited[i]
&& dfs(graph, i, onpath, visited, toposort))
return new ArrayList<Integer>();
Collections.reverse(toposort);
return toposort;
}
// Driver code
public static void main(String[] args)
{
int numTasks = 4;
int[][] prerequisites
= { { 1, 0 }, { 2, 1 }, { 3, 2 } };
ArrayList<Integer> v
= findOrder(numTasks, prerequisites);
for (int i = 0; i < v.size(); i++) {
System.out.print(v.get(i) + " ");
}
}
}
// This code is contributed by Lovely Jain
0 1 2 3
Referencia: https://leetcode.com/problems/course-schedule-ii/
Publicación traducida automáticamente
Artículo escrito por shashipk11 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA