Encuentra las dependencias de cada vértice en un gráfico dirigido

Dado un grafo dirigido que contiene N vértices y M aristas, la tarea es encontrar todas las dependencias de cada vértice en el grafo y el vértice con la mínima dependencia.
 

Un gráfico dirigido (o dígrafo) es un conjunto de Nodes conectados por aristas, donde las aristas tienen una dirección asociada con ellos. 
Por ejemplo, se considera que un arco (x, y) está dirigido de x a y, y el arco (y, x) es el vínculo invertido. Y es un sucesor directo de x, y x es un predecesor directo de y. 
La dependencia es el número de conexiones a diferentes vértices que dependen del vértice actual. 
 

Ejemplos: 
 

Aporte: 
 

Salida: 
Dependencias de vértice 1 -> 2-> 3 
Dependencias de vértice 2 -> 3-> 1 
Dependencias de vértice 3 -> 1-> 2 
El Node 1 tiene el número mínimo de dependencia de 2. 
Explicación: 
El vértice 1 depende de 2 y 3 Del mismo modo , 
el vértice 2 y 3 en (3, 1) y (1, 2) respectivamente. 
Por lo tanto, el número mínimo de dependencia entre todos los vértices es 2. 
Entrada: 
 

Salida: 
Dependencia de vértice 1 -> 2-> 3-> 4-> 5-> 6  Dependencia de
vértice 2 -> 6 
Dependencia de vértice 3 -> 4-> 5-> 6 
Dependencia de vértice 4 -> 5-> 6 
Dependencia de vértice 5 -> 6 
El vértice 6 no depende de ningún vértice. 
El Node 6 tiene una dependencia mínima de 0. 
Explicación: 
el vértice 1 depende de (3, 4, 5, 6, 7). De manera similar, el vértice 2 en (6), el vértice 3 en (4, 5, 6), el vértice 4 en (5, 6), el vértice 5 en (6) y el vértice 6 no dependen de ninguno. 
Por lo tanto, el número mínimo de dependencia entre todos los vértices es 0. 
 

Enfoque: La idea es utilizar la búsqueda en profundidad (DFS) para resolver este problema. 
 

• Obtenga el gráfico dirigido como entrada.
• Realice el DFS en el gráfico y explore todos los Nodes del gráfico.
• Mientras explora los vecinos del Node, agregue 1 para contar y finalmente devuelva el recuento que significa el número de dependencias.
• Finalmente, encuentre el Node con el número mínimo de dependencias.

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

// C++ program to find the
// dependency of each node
 
#include <bits/stdc++.h>
using namespace std;
 
// Defining the graph
class Graph {
 
    // Variable to store the
    // number of vertices
    int V;
 
    // Adjacency list
    list<int>* adjList;
 
    // Initializing the graph
public:
    Graph(int v)
    {
        V = v;
        adjList = new list<int>[V];
    }
 
    // Adding edges
    void addEdge(int u, int v,
                 bool bidir = true)
    {
        adjList[u].push_back(v);
        if (bidir) {
            adjList[u].push_back(v);
        }
    }
 
    // Performing DFS on each node
    int dfs(int src)
    {
        // Map is used to mark
        // the current node as visited
        map<int, bool> visited;
        vector<int> dependent;
        int count = 0;
 
        stack<int> s;
 
        // Push the current vertex
        // to the stack which
        // stores the result
        s.push(src);
 
        visited[src] = true;
 
        // Traverse through the vertices
        // until the stack is empty
        while (!s.empty()) {
            int n = s.top();
            s.pop();
 
            // Recur for all the vertices
            // adjacent to this vertex
            for (auto i : adjList[n]) {
 
                // If the vertices are
                // not visited
                if (!visited[i]) {
                    dependent.push_back(i + 1);
                    count++;
 
                    // Mark the vertex as
                    // visited
                    visited[i] = true;
 
                    // Push the current vertex to
                    // the stack which stores
                    // the result
                    s.push(i);
                }
            }
        }
 
        // If the vertex has 0 dependency
        if (!count) {
            cout << "Vertex " << src + 1
                 << " is not dependent on any vertex.\n";
            return count;
        }
 
        cout << "Vertex " << src + 1 << " dependency ";
        for (auto i : dependent) {
            cout << "-> " << i;
        }
        cout << "\n";
        return count;
    }
};
 
// Function to find the
// dependency of each node
void operations(int arr[][2],
                int n, int m)
{
    // Creating a new graph
    Graph g(n);
 
    for (int i = 0; i < m; i++) {
        g.addEdge(arr[i][0],
                  arr[i][1], false);
    }
 
    int ans = INT_MAX;
    int node = 0;
 
    // Iterating through the graph
    for (int i = 0; i < n; i++) {
        int c = g.dfs(i);
 
        // Finding the node with
        // minimum number of
        // dependency
        if (c < ans) {
            ans = c;
            node = i + 1;
        }
    }
    cout << "Node " << node
         << "has minimum dependency of "
         << ans;
}
 
// Driver code
int main()
{
    int n, m;
 
    n = 6, m = 6;
 
    // Defining the edges of the
    // graph
    int arr[][2] = { { 0, 1 },
                     { 0, 2 },
                     { 2, 3 },
                     { 4, 5 },
                     { 3, 4 },
                     { 1, 5 } };
 
    operations(arr, n, m);
 
    return 0;
}

# Python3 program to find the
# dependency of each node
 
# Adding edges
def addEdge(u, v, bidir = True):
    global adjList
    adjList[u].append(v)
    if (bidir):
        adjList[u].append(v)
 
# Performing DFS on each node
def dfs(src):
    global adjList, V
     
    # Map is used to mark
    # the current node as visited
    visited = [False for i in range(V+1)]
    dependent = []
    count = 0
    s = []
 
    # Push the current vertex
    # to the stack which
    # stores the result
    s.append(src)
    visited[src] = True
 
    # Traverse through the vertices
    # until the stack is empty
    while (len(s) > 0):
        n = s[-1]
        del s[-1]
 
        # Recur for all the vertices
        # adjacent to this vertex
        for i in adjList[n]:
 
            # If the vertices are
            # not visited
            if (not visited[i]):
                dependent.append(i + 1)
                count += 1
 
                # Mark the vertex as
                # visited
                visited[i] = True
 
                # Push the current vertex to
                # the stack which stores
                # the result
                s.append(i)
 
    # If the vertex has 0 dependency
    if (not count):
        print("Vertex ", src + 1,
              " is not dependent on any vertex.")
        return count
 
    print("Vertex ",src + 1," dependency ",end="")
    for i in dependent:
        print("-> ", i, end = "")
    print()
    return count
 
# Function to find the
# dependency of each node
def operations(arr, n, m):
   
    # Creating a new graph
    global adjList
    for i in range(m):
        addEdge(arr[i][0], arr[i][1], False)
    ans = 10**18
    node = 0
 
    # Iterating through the graph
    for i in range(n):
        c = dfs(i)
 
        # Finding the node with
        # minimum number of
        # dependency
        if (c < ans):
            ans = c
            node = i + 1
    print("Node", node, "has minimum dependency of ", ans)
 
# Driver code
if __name__ == '__main__':
    V = 6
    adjList = [[] for i in range(V+1)]
    n, m = 6, 6
 
 
    # Defining the edges of the
    # graph
    arr = [ [ 0, 1 ],
             [ 0, 2 ],
             [ 2, 3 ],
             [ 4, 5 ],
             [ 3, 4 ],
             [ 1, 5 ] ]
 
    operations(arr, n, m)
 
    # This code is contributed by mohit kumar 29.

Vertex 1 dependency -> 2-> 3-> 4-> 5-> 6
Vertex 2 dependency -> 6
Vertex 3 dependency -> 4-> 5-> 6
Vertex 4 dependency -> 5-> 6
Vertex 5 dependency -> 6
Vertex 6 is not dependent on any vertex.
Node 6has minimum dependency of 0