Dado un gráfico acíclico dirigido que tiene V vértices y E aristas, donde cada arista {U, V} representa los trabajos U y V , de modo que el trabajo V solo puede iniciarse después de completar el trabajo U. La tarea es determinar el tiempo mínimo que tarda cada trabajo en completarse, donde cada trabajo requiere una unidad de tiempo para completarse.
Ejemplos:
Entrada: N = 10, E = 13, a continuación se muestra el gráfico dado:
Salida: 1 1 2 2 2 3 4 5 2 6
Explicación:
Comience los trabajos 1 y 2 al principio y complételos en 1 unidad de tiempo.
Dado que los trabajos 3, 4, 5 y 9 tienen la única dependencia de un trabajo (es decir, el primer trabajo para los trabajos 3, 4 y 5 y el segundo trabajo para el trabajo 9). Entonces, podemos comenzar estos trabajos en la primera unidad de tiempo y completarlos en la segunda unidad de tiempo después de completar el trabajo dependiente.
Del mismo modo,
el trabajo 6 solo se puede realizar después de que se hayan realizado el tercer y el cuarto trabajo. Por lo tanto, comience en la segunda unidad de tiempo y complételo en la tercera unidad de tiempo.
El trabajo 7 solo se puede realizar después de que se haya realizado el trabajo 6. Entonces, puede comenzarlo en la 3ra unidad de tiempo y completarlo en la 4ta unidad de tiempo.
El trabajo 8 solo se puede realizar después de que se hayan realizado los trabajos 4, 5 y 7. Entonces, comience en la cuarta unidad de tiempo y complételo en la quinta unidad de tiempo.
El trabajo 10 solo se puede realizar después de que se haya realizado el octavo trabajo. Entonces, comience en la quinta unidad de tiempo y complételo en la sexta unidad de tiempo.Entrada: N = 7, E = 7, A continuación se muestra el gráfico dado:
Salida: 1 2 3 3 3 4 4
Explicación:
Inicie el trabajo 1 desde el principio y complételo en la primera unidad de tiempo.
El trabajo 2 solo se puede realizar después de que se haya realizado el 1.er trabajo. Entonces, comience en la primera unidad de tiempo y complételo en la segunda unidad de tiempo.
Dado que Job 3, 4 y 5 tienen la única dependencia del 2nd Job. Por lo tanto, comience estos trabajos en la segunda unidad de tiempo y complételos en la tercera unidad de tiempo.
El trabajo 6 solo se puede realizar después de que se hayan realizado el trabajo 3 y 4. Entonces, comience en la 3ra unidad de tiempo y complétela en la 4ta unidad de tiempo.
El trabajo 7 solo se puede realizar después de que se haya realizado el trabajo 5. Por lo tanto, comience en la 3.ª hora y complételo en la 4.ª unidad de tiempo.
Enfoque: el trabajo se puede iniciar solo si todos los trabajos que son requisitos previos del trabajo se han realizado. Por lo tanto, la idea es utilizar Ordenación topológica para la red dada. A continuación se muestran los pasos:
- Finalice los trabajos que no dependan de ningún otro trabajo.
- Cree una array en Grado[] para almacenar el recuento del Node dependiente para cada Node en la red dada.
- Inicialice una cola y empuje todos los vértices cuyo inDegree[] sea 0.
- Inicialice el temporizador a 1 y almacene el tamaño actual de la cola (por ejemplo, tamaño ) y haga lo siguiente:
- Extraiga el Node de la cola hasta que el tamaño sea 0 y actualice la hora de finalización de este Node en el temporizador .
- Mientras extrae el Node (digamos Node U ) de la cola, disminuya el grado de cada Node conectado a él.
- Si el grado de cualquier Node es 0 en el paso anterior, inserte ese Node en la cola.
- Incremente el temporizador después de todos los pasos anteriores.
- Imprima el tiempo de finalización de todos los Nodes después de atravesar cada Node en el paso anterior.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
#define maxN 100000
// Adjacency List to store the graph
vector<int> graph[maxN];
// Array to store the in-degree of node
int indegree[maxN];
// Array to store the time in which
// the job i can be done
int job[maxN];
// Function to add directed edge
// between two vertices
void addEdge(int u, int v)
{
// Insert edge from u to v
graph[u].push_back(v);
// Increasing the indegree
// of vertex v
indegree[v]++;
}
// Function to find the minimum time
// needed by each node to get the task
void printOrder(int n, int m)
{
// Find the topo sort order
// using the indegree approach
// Queue to store the
// nodes while processing
queue<int> q;
// Pushing all the vertex in the
// queue whose in-degree is 0
// Update the time of the jobs
// who don't require any job to
// be completed before this job
for (int i = 1; i <= n; i++) {
if (indegree[i] == 0) {
q.push(i);
job[i] = 1;
}
}
// Iterate until queue is empty
while (!q.empty()) {
// Get front element of queue
int cur = q.front();
// Pop the front element
q.pop();
for (int adj : graph[cur]) {
// Decrease in-degree of
// the current node
indegree[adj]--;
// Push its adjacent elements
if (indegree[adj] == 0) {
job[adj] = job[cur] + 1;
q.push(adj);
}
}
}
// Print the time to complete
// the job
for (int i = 1; i <= n; i++)
cout << job[i] << " ";
cout << "\n";
}
// Driver Code
int main()
{
// Given Nodes N and edges M
int n, m;
n = 10;
m = 13;
// Given Directed Edges of graph
addEdge(1, 3);
addEdge(1, 4);
addEdge(1, 5);
addEdge(2, 3);
addEdge(2, 8);
addEdge(2, 9);
addEdge(3, 6);
addEdge(4, 6);
addEdge(4, 8);
addEdge(5, 8);
addEdge(6, 7);
addEdge(7, 8);
addEdge(8, 10);
// Function Call
printOrder(n, m);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static final int maxN = 100000;
// Adjacency List to store the graph
@SuppressWarnings("unchecked")
static Vector<Integer> []graph = new Vector[maxN];
// Array to store the in-degree of node
static int []indegree = new int[maxN];
// Array to store the time in which
// the job i can be done
static int []job = new int[maxN];
// Function to add directed edge
// between two vertices
static void addEdge(int u, int v)
{
// Insert edge from u to v
graph[u].add(v);
// Increasing the indegree
// of vertex v
indegree[v]++;
}
// Function to find the minimum time
// needed by each node to get the task
static void printOrder(int n, int m)
{
// Find the topo sort order
// using the indegree approach
// Queue to store the
// nodes while processing
Queue<Integer> q = new LinkedList<>();
// Pushing all the vertex in the
// queue whose in-degree is 0
// Update the time of the jobs
// who don't require any job to
// be completed before this job
for(int i = 1; i <= n; i++)
{
if (indegree[i] == 0)
{
q.add(i);
job[i] = 1;
}
}
// Iterate until queue is empty
while (!q.isEmpty())
{
// Get front element of queue
int cur = q.peek();
// Pop the front element
q.remove();
for(int adj : graph[cur])
{
// Decrease in-degree of
// the current node
indegree[adj]--;
// Push its adjacent elements
if (indegree[adj] == 0){
job[adj] = 1 + job[cur];
q.add(adj);
}
}
}
// Print the time to complete
// the job
for(int i = 1; i <= n; i++)
System.out.print(job[i] + " ");
System.out.print("\n");
}
// Driver Code
public static void main(String[] args)
{
// Given Nodes N and edges M
int n, m;
n = 10;
m = 13;
for(int i = 0; i < graph.length; i++)
graph[i] = new Vector<Integer>();
// Given directed edges of graph
addEdge(1, 3);
addEdge(1, 4);
addEdge(1, 5);
addEdge(2, 3);
addEdge(2, 8);
addEdge(2, 9);
addEdge(3, 6);
addEdge(4, 6);
addEdge(4, 8);
addEdge(5, 8);
addEdge(6, 7);
addEdge(7, 8);
addEdge(8, 10);
// Function call
printOrder(n, m);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach from collections import defaultdict # Class to represent a graph class Graph: def __init__(self, vertices, edges): # Dictionary containing adjacency List self.graph = defaultdict(list) # No. of vertices self.n = vertices # No. of edges self.m = edges # Function to add an edge to graph def addEdge(self, u, v): self.graph[u].append(v) # Function to find the minimum time # needed by each node to get the task def printOrder(self, n, m): # Create a vector to store indegrees of all # vertices. Initialize all indegrees as 0. indegree = [0] * (self.n + 1) # Traverse adjacency lists to fill indegrees # of vertices. This step takes O(V + E) time for i in self.graph: for j in self.graph[i]: indegree[j] += 1 # Array to store the time in which # the job i can be done job = [0] * (self.n + 1) # Create an queue and enqueue all # vertices with indegree 0 q = [] # Update the time of the jobs # who don't require any job to # be completed before this job for i in range(1, self.n + 1): if indegree[i] == 0: q.append(i) job[i] = 1 # Iterate until queue is empty while q: # Get front element of queue cur = q.pop(0) for adj in self.graph[cur]: # Decrease in-degree of # the current node indegree[adj] -= 1 # Push its adjacent elements if (indegree[adj] == 0): job[adj] = 1 + job[cur] q.append(adj) # Print the time to complete # the job for i in range(1, n + 1): print(job[i], end = " ") print() # Driver Code # Given Nodes N and edges M n = 10 m = 13 g = Graph(n, m) # Given Directed Edges of graph g.addEdge(1, 3) g.addEdge(1, 4) g.addEdge(1, 5) g.addEdge(2, 3) g.addEdge(2, 8) g.addEdge(2, 9) g.addEdge(3, 6) g.addEdge(4, 6) g.addEdge(4, 8) g.addEdge(5, 8) g.addEdge(6, 7) g.addEdge(7, 8) g.addEdge(8, 10) # Function Call g.printOrder(n, m) # This code is contributed by Aanchal Tiwari
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
static readonly int maxN = 100000;
// Adjacency List to store the graph
static List<int> []graph = new List<int>[maxN];
// Array to store the in-degree of node
static int []indegree = new int[maxN];
// Array to store the time in which
// the job i can be done
static int []job = new int[maxN];
// Function to add directed edge
// between two vertices
static void addEdge(int u, int v)
{
// Insert edge from u to v
graph[u].Add(v);
// Increasing the indegree
// of vertex v
indegree[v]++;
}
// Function to find the minimum time
// needed by each node to get the task
static void printOrder(int n, int m)
{
// Find the topo sort order
// using the indegree approach
// Queue to store the
// nodes while processing
Queue<int> q = new Queue<int>();
// Pushing all the vertex in the
// queue whose in-degree is 0
// Update the time of the jobs
// who don't require any job to
// be completed before this job
for(int i = 1; i <= n; i++)
{
if (indegree[i] == 0)
{
q.Enqueue(i);
job[i] = 1;
}
}
// Iterate until queue is empty
while (q.Count != 0)
{
// Get front element of queue
int cur = q.Peek();
// Pop the front element
q.Dequeue();
foreach(int adj in graph[cur])
{
// Decrease in-degree of
// the current node
indegree[adj]--;
// Push its adjacent elements
if (indegree[adj] == 0){
job[adj] = 1 + job[cur];
q.Enqueue(adj);
}
}
}
// Print the time to complete
// the job
for(int i = 1; i <= n; i++)
Console.Write(job[i] + " ");
Console.Write("\n");
}
// Driver Code
public static void Main(String[] args)
{
// Given Nodes N and edges M
int n, m;
n = 10;
m = 13;
for(int i = 0; i < graph.Length; i++)
graph[i] = new List<int>();
// Given directed edges of graph
addEdge(1, 3);
addEdge(1, 4);
addEdge(1, 5);
addEdge(2, 3);
addEdge(2, 8);
addEdge(2, 9);
addEdge(3, 6);
addEdge(4, 6);
addEdge(4, 8);
addEdge(5, 8);
addEdge(6, 7);
addEdge(7, 8);
addEdge(8, 10);
// Function call
printOrder(n, m);
}
}
// This code is contributed by Amit Katiyar
1 1 2 2 2 3 4 5 2 6
Complejidad temporal: O(V+E), donde V es el número de Nodes y E es el número de aristas.
Espacio Auxiliar: O(V)
Publicación traducida automáticamente
Artículo escrito por pwnkumar0786 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA