Imprimir tareas completadas al final según Dependencias

Dadas N dependencias de la forma XY , donde X e Y representan dos tareas diferentes. La dependencia XY denota dependencia de la forma Y -> X , es decir, si la tarea Y ocurre, entonces la tarea X ocurrirá, en otras palabras, la tarea Y debe completarse primero para iniciar la tarea X. También se dan M tareas que se iniciarán primero. La tarea es imprimir todas las tareas que se completarán al final en el orden lexicográfico . Tenga en cuenta que las tareas se representarán solo con letras mayúsculas en inglés.

Entrada: dep[][] = {{A, B}, {C, B}, {D, A}, {D, C}, {B, E}}, tareas[] = {B, C}
Salida : ABCD
La tarea A ocurre después de la tarea B y la tarea D solo puede ocurrir
después de completar las tareas A o C.
Por lo tanto, el orden requerido es ABC D.

Entrada: dep[][] = {{Q, P}, {S, Q}, {Q, R}}, tareas[] = {R}
Salida: QRS

Enfoque: DFS se puede utilizar para resolver el problema. Las dependencias de la forma XY (Y -> X) se pueden representar como un borde desde el Node Y hasta el Node X en el gráfico. Inicie el DFS desde cada uno de los M Nodes iniciales y marque los Nodes que se encuentran como visitados utilizando una array booleana. Por último, imprima los Nodes/tareas que se cubren usando DFS en orden lexicográfico. El enfoque funciona porque DFS cubrirá todos los Nodes a partir de los Nodes iniciales de manera secuencial.

Considere el siguiente diagrama que representa el primer ejemplo de lo anterior:

El diagrama muestra los bordes cubiertos durante DFS de las tareas iniciales B y C en
color rojo. Los Nodes así visitados fueron A, B, C y D.

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation of the approach
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
  
// Graph class represents a directed graph
// using adjacency list representation
class Graph {
  
    // Number of vertices
    int V;
  
    // Pointer to an array containing
    // adjacency lists
    vector<int>* adj;
  
    // Boolean array to mark tasks as visited
    bool visited[26];
  
    // A recursive function used by DFS
    void DFSUtil(int v);
  
public:
    // Constructor
    Graph()
    {
  
        // There are only 26 English
        // upper case letters
        this->V = 26;
        adj = new vector<int>[26];
    }
  
    // Function to add an edge to the graph
    void addEdge(char v, char w);
  
    // DFS traversal of the vertices
    // reachable from v
    void DFS(char start[], int M);
  
    void printTasks();
};
  
// Function to add an edge to the graph
void Graph::addEdge(char v, char w)
{
  
    // Add w to v's list
    adj[v - 65].push_back(w - 65);
}
  
void Graph::DFSUtil(int v)
{
  
    // Mark the current node as visited and
    // print it
    visited[v] = true;
  
    // Recur for all the vertices adjacent
    // to this vertex
    vector<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            DFSUtil(*i);
}
  
// DFS traversal of the vertices reachable
// from start nodes
// It uses recursive DFSUtil()
void Graph::DFS(char start[], int M)
{
    // Mark all the vertices as not visited
    for (int i = 0; i < V; i++)
        visited[i] = false;
  
    // Call the recursive helper function
    // to print DFS traversal
    for (int i = 0; i < M; i++)
        DFSUtil(start[i] - 65);
}
  
// Helper function to print the tasks in
// lexicographical order that are completed
// at the end of the DFS
void Graph::printTasks()
{
    for (int i = 0; i < 26; i++) {
        if (visited[i])
            cout << char(i + 65) << " ";
    }
    cout << endl;
}
  
// Driver code
int main()
{
    // Create the graph
    Graph g;
    g.addEdge('B', 'A');
    g.addEdge('B', 'C');
    g.addEdge('A', 'D');
    g.addEdge('C', 'D');
    g.addEdge('E', 'B');
  
    // Initial tasks to be run
    char start[] = { 'B', 'C' };
    int n = sizeof(start) / sizeof(char);
  
    // Start the dfs
    g.DFS(start, n);
  
    // Print the tasks that will get finished
    g.printTasks();
  
    return 0;
}

# Python3 implementation of the approach
from collections import defaultdict 
  
# This class represents a directed graph 
# using adjacency list representation 
class Graph: 
  
    # Constructor 
    def __init__(self): 
  
        # Default dictionary to store the graph 
        self.graph = defaultdict(list) 
        self.visited = [False]*26
  
    # Function to add an edge to the graph 
    def addEdge(self, u, v): 
        self.graph[ord(u)-65].append(ord(v)-65) 
  
    # A function used by DFS 
    def DFSUtil(self, v): 
          
        # Mark the current node as visited 
        # and print it 
        self.visited[v]= True
  
        # Recur for all the vertices adjacent 
        # to this vertex 
        for i in self.graph[v]: 
            if self.visited[i] == False: 
                self.DFSUtil(i) 
  
  
    # Function to perform the DFS traversal 
    # It uses recursive DFSUtil() 
    def DFS(self, start, M): 
          
        # Total vertices 
        V = len(self.graph)
          
        # Call the recursive helper function 
        # to print the DFS traversal starting 
        # from all vertices one by one 
        for i in range(M):
            self.DFSUtil(ord(start[i])-65) 
      
    def printOrder(self):
        for i in range(26):
            if self.visited[i] == True:
                print(chr(i + 65), end =" ")
        print("\n")
  
# Driver code 
g = Graph() 
g.addEdge('B', 'A') 
g.addEdge('B', 'C') 
g.addEdge('A', 'D') 
g.addEdge('C', 'D') 
g.addEdge('E', 'B') 
  
g.DFS(['B', 'C'], 2) 
g.printOrder()

A B C D

Complejidad temporal: O(V + E) donde V es el número de Nodes en el gráfico y E es el número de aristas o dependencias. En este caso, dado que V siempre es 26, la complejidad temporal es O(26 + E) o simplemente O(E) en el peor de los casos.
Complejidad espacial: O(V + E)