Encuentre los Dominadores para cada vértice en un DAG dado (Gráfico acíclico dirigido)

Dado un gráfico acíclico dirigido con vértices V y aristas E , la tarea es encontrar el conjunto de vértices dominantes para cada vértice del gráfico.

¿Qué son los dominadores en la teoría de grafos? En los gráficos de flujo de control, un vértice V1 es el dominador de otro vértice V2 si todas las rutas desde el vértice de origen (en este caso, el vértice ‘0’) hasta el vértice V2 pasan por V1 . Por definición, cada vértice es uno de sus propios dominadores.

Ejemplos:

Entrada: V = 5, E = 5, adj[][] = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}}
Salida:
Dominante Conjunto de vértices: 0 –> 0 
Conjunto dominante de vértices: 1 –> 0 1 
Conjunto dominante de vértices: 2 –> 0 2 
Conjunto dominante de vértices: 3 –> 0 3 
Conjunto dominante de vértices: 4 –> 0 3 4
Explicación :
          0
       / \
     1 2
      \ /
         3
         |
        4          
Aquí 0 es el Node de entrada, por lo que su dominador es 0 mismo.
Solo existe un camino entre (0, 1), por lo que los dominadores de 1 son 0, 1.
Solo existe un camino entre (0, 2), por lo que los dominadores de 2 son 0, 2.
Hay 2 caminos entre (0, 3) que tienen solo 0, 3 en común.
De (0, 4) hay 2 caminos (0 1 3 4) y (0 2 3 4) con 0, 3 y 4 en común.

Entrada: V = 4, E = 3, adj[][] = {{0, 1}, {0, 2}, {3, 2}}
Salida:
Conjunto dominante de vértice: 0 –> 0 
Conjunto dominante de vértice : 1 –> 0 1 
Conjunto dominante de vértice: 2 –> 0 2 
Conjunto dominante de vértice: 3 –> 0 2 3

Enfoque: La idea es realizar DFS y mantener un conjunto de todos los dominadores de cada vértice. Siga los pasos a continuación para resolver el problema:

• Inicialice un vector de estructura de datos de conjunto de bits, digamos b para almacenar el conjunto de todos los dominadores de los vértices.
• Para cada Node i , los bits establecidos en b[i] representarán el conjunto de vértices dominantes de i. 
• Para encontrar los dominadores de cada vértice, es importante encontrar todos los caminos en un gráfico acíclico dirigido .
• Recorra el gráfico usando DFS para encontrar todos los caminos en el gráfico .
• Inicie el recorrido desde el Node raíz, es decir , 0
• Mientras realiza DFS , para cada vértice i
  • Si el Node aún no ha sido visitado , establezca todos los bits de b[i] y marque el Node visitado
  • Almacene el conjunto de vértices dominantes en el conjunto de bits b[i] como la intersección del conjunto de vértices dominantes de su padre. Actualice b[i] a b[i] & b[parent] .
  • Actualice el valor de b[i][i] a 1 porque cada Node es un dominador de sí mismo.
  • De forma recursiva , llame a DFS para los Nodes secundarios de i .
• Después de realizar los pasos anteriores, imprima los vértices dominantes para el vértice, es decir, la posición de los bits establecidos en b[i] .

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Declare bitsets for each
// vertex to store the set of
// dominant vertices
vector<bitset<100> > b(100);
 
// Visited array to check if
// a vertex has been visited or not
int vis[100] = {};
 
// Function to find set of dominator
// vertices for a particular node
void findDominator(vector<vector<int> > graph,
                   bitset<100> par, int node)
{
    // If node is unvisited
    if (vis[node] == 0) {
        // Set all bits of b[pos]
        b[node] = ~b[node];
 
        // Update vis[node] to 1
        vis[node] = 1;
    }
 
    // Update b[node] with bitwise and
    // of parent's dominant vertices
    b[node] &= par;
 
    // Node is itself is a
    // dominant vertex of node
    b[node][node] = 1;
 
    // Traverse the neighbours of node
    for (int i = 0; i < (int)graph[node].size(); i++) {
       
        // Recursive function call to
        //  children nodes of node
        findDominator(graph, b[node], graph[node][i]);
    }
}
 
// Function to build the graph
void buildGraph(vector<pair<int, int> > adj, int E, int V)
{
    // Vector of vector to store
    // the adjacency matrix
    vector<vector<int> > graph(V + 1);
 
    // Build the adjacency matrix
    for (int i = 0; i < E; i++) {
        graph[adj[i].first].push_back(adj[i].second);
    }
 
    // Bitset for node 0
    bitset<100> g;
 
    // Node 0 itself is a dominant
    // vertex of itself
    g[0] = 1;
 
    // Update visited of source
    // node as true
    vis[0] = 1;
 
    // DFS from source vertex
    findDominator(graph, g, 0);
}
 
// Function to find dominant set of vertices
void dominantVertices(int V, int E,
                      vector<pair<int, int> > adj)
{
    // Function call to build the graph
    // and dominant vertices
    buildGraph(adj, E, V);
 
    // Print set of dominating vertices
    for (int i = 0; i < V; i++) {
        cout << i << " -> ";
        for (int j = 0; j < V; j++) {
            if (b[i][j] == 1)
                cout << j << " ";
        }
        cout << endl;
    }
}
 
// Driver Code
int main()
{
    // Given Input
    int V = 5, E = 5;
    vector<pair<int, int> > adj = {
        { 0, 1 }, { 0, 2 }, { 1, 3 }, { 2, 3 }, { 3, 4 }
    };
 
    // Function Call
    dominantVertices(V, E, adj);
 
    return 0;
}

0 -> 0 
1 -> 0 1 
2 -> 0 2 
3 -> 0 3 
4 -> 0 3 4 

Complejidad Temporal: O(V ³ )
Espacio Auxiliar: O(V ² )