Bordes máximos que se pueden agregar a DAG para que siga siendo DAG

Se nos da un DAG, necesitamos encontrar el número máximo de aristas que se pueden agregar a este DAG, después de lo cual el nuevo gráfico sigue siendo un DAG, lo que significa que el gráfico reformado debe tener la cantidad máxima de aristas, agregar incluso un solo borde creará un ciclo en el gráfico.

The Output for above example should be following edges in any order.
4-2, 4-5, 4-3, 5-3, 5-1, 2-0, 2-1, 0-3, 0-1

Como se muestra en el ejemplo anterior, hemos agregado todos los bordes en una sola dirección para evitar hacer un ciclo. Este es el truco para resolver esta pregunta. Clasificamos todos nuestros Nodes en orden topológico y creamos bordes desde el Node a todos los Nodes a la derecha si aún no están allí. 
¿Cómo podemos decir que no es posible agregar más borde? la razón es que hemos agregado todos los bordes posibles de izquierda a derecha y si queremos agregar más bordes debemos hacerlo de derecha a izquierda, pero al agregar bordes de derecha a izquierda seguramente creamos un ciclo porque su contraparte es de izquierda a derecha El borde ya se ha agregado al gráfico y crear un ciclo no es lo que necesitábamos. 
Entonces, la solución procede de la siguiente manera, consideramos los Nodes en orden topológico y si algún borde no está allí de izquierda a derecha, lo crearemos. 

A continuación se muestra la solución, hemos impreso todos los bordes que se pueden agregar a un DAG dado sin realizar ningún ciclo. 

// C++ program to find maximum edges after adding
// which graph still remains a DAG
#include <bits/stdc++.h>
using namespace std;
 
class Graph {
    int V; // No. of vertices
 
    // Pointer to a list containing adjacency list
    list<int>* adj;
 
    // Vector to store indegree of vertices
    vector<int> indegree;
 
    // function returns a topological sort
    vector<int> topologicalSort();
 
public:
    Graph(int V); // Constructor
 
    // function to add an edge to graph
    void addEdge(int v, int w);
 
    // Prints all edges that can be added without making any
    // cycle
    void maximumEdgeAddtion();
};
 
//  Constructor of graph
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
 
    // Initialising all indegree with 0
    for (int i = 0; i < V; i++)
        indegree.push_back(0);
}
 
//  Utility function to add edge
void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); // Add w to v's list.
 
    // increasing inner degree of w by 1
    indegree[w]++;
}
 
//  Main function to print maximum edges that can be added
vector<int> Graph::topologicalSort()
{
    vector<int> topological;
    queue<int> q;
 
    //  In starting push all node with indegree 0
    for (int i = 0; i < V; i++)
        if (indegree[i] == 0)
            q.push(i);
 
    while (!q.empty()) {
        int t = q.front();
        q.pop();
 
        //  push the node into topological vector
        topological.push_back(t);
 
        //  reducing indegree of adjacent vertices
        for (list<int>::iterator j = adj[t].begin();
             j != adj[t].end(); j++) {
            indegree[*j]--;
 
            //  if indegree becomes 0, just push
            // into queue
            if (indegree[*j] == 0)
                q.push(*j);
        }
    }
    return topological;
}
 
//  The function prints all edges that can be
//  added without making any cycle
//  It uses recursive topologicalSort()
void Graph::maximumEdgeAddtion()
{
    bool* visited = new bool[V];
    vector<int> topo = topologicalSort();
 
    //  looping for all nodes
    for (int i = 0; i < topo.size(); i++) {
        int t = topo[i];
 
        //  In below loop we mark the adjacent node of t
        for (list<int>::iterator j = adj[t].begin();
             j != adj[t].end(); j++)
            visited[*j] = true;
 
        //  In below loop unmarked nodes are printed
        for (int j = i + 1; j < topo.size(); j++) {
            // if not marked, then we can make an edge
            // between t and j
            if (!visited[topo[j]])
                cout << t << "-" << topo[j] << " ";
 
            visited[topo[j]] = false;
        }
    }
}
 
// Driver code to test above methods
int main()
{
    // Create a graph given in the above diagram
    Graph g(6);
    g.addEdge(5, 2);
    g.addEdge(5, 0);
    g.addEdge(4, 0);
    g.addEdge(4, 1);
    g.addEdge(2, 3);
    g.addEdge(3, 1);
 
    g.maximumEdgeAddtion();
    return 0;
}

// Java program to find maximum edges after adding
// which graph still remains a DAG
import java.util.*;
 
public class Graph {
 
  int V;   // No. of vertices
 
  ArrayList<ArrayList<Integer>> adj;  // adjacency list
 
  // array to store indegree of vertices
  int[] indegree;
 
  //  Constructor of graph
  Graph(int v)
  {
    this.V = v;
    indegree = new int[V];
    adj = new ArrayList<>(V);
 
    for(int i = 0; i < V; i++)
    {
      adj.add(new ArrayList<Integer>());
      indegree[i] = 0;
    }
  }
 
  //  Utility function to add edge
  public void addEdge(int v,int w)
  {
    adj.get(v).add(w);// Add w to v's list.
 
    // increasing inner degree of w by 1
    indegree[w]++;
  }
 
  //  Main function to print maximum edges that can be added
  public List<Integer> topologicalSort() 
  {
 
    List<Integer> topological = new ArrayList<>(V);
    Queue<Integer> q = new LinkedList<>();
 
    //  In starting push all node with indegree 0
    for(int i = 0; i < V; i++)
    {
      if(indegree[i] == 0)
      {
        q.add(i);
      }
    }
 
 
    while(!q.isEmpty())
    {
      int t=q.poll();
 
      //  push the node into topological list
      topological.add(t);
 
      //  reducing inDegree of adjacent vertical       
      for(int j: adj.get(t))
      {
        indegree[j]--;
 
        //  if inDegree becomes 0, just push
        // into queue
        if(indegree[j] == 0)
        {
          q.add(j);
        }
      }
 
    }
 
    return topological;
 
  }
 
  //  The function prints all edges that can be
  //  added without making any cycle
  //  It uses recursive topologicalSort()
  public void maximumEdgeAddtion()
  {
    boolean[] visited = new boolean[V];
    List<Integer> topo=topologicalSort();
 
    //  looping for all nodes
    for(int i = 0; i < topo.size(); i++)
    {
      int t = topo.get(i);
 
      //  In below loop we mark the adjacent node of t
      for( Iterator<Integer> j = adj.get(t).listIterator();j.hasNext();)
      {
        visited[j.next()] = true;
      }
 
      for(int j = i + 1; j < topo.size(); j++)
      {
        // if not marked, then we can make an edge
        // between t and j
        if(!visited[topo.get(j)])
        {
          System.out.print( t  + "-" + topo.get(j) + " ");
        }
 
        visited[topo.get(j)] = false;
      }
    }
  }
 
  // Driver code to test above methods
  public static void main(String[] args)
  {    
 
    // Create a graph given in the above diagram
    Graph g = new Graph(6);
    g.addEdge(5, 2);
    g.addEdge(5, 0);
    g.addEdge(4, 0);
    g.addEdge(4, 1);
    g.addEdge(2, 3);
    g.addEdge(3, 1);
 
    g.maximumEdgeAddtion();
    return ;
  }   
}
 
// This code is contributed by sameergupta22.

# Python3 program to find maximum
# edges after adding which graph
# still remains a DAG
 
 
class Graph:
 
    def __init__(self, V):
 
        # No. of vertices
        self.V = V
 
        # Pointer to a list containing
        # adjacency list
        self.adj = [[] for i in range(V)]
 
        # Vector to store indegree of vertices
        self.indegree = [0 for i in range(V)]
 
    # Utility function to add edge
    def addEdge(self, v, w):
 
         # Add w to v's list.
        self.adj[v].append(w)
 
        # Increasing inner degree of w by 1
        self.indegree[w] += 1
 
    # Main function to print maximum
    # edges that can be added
    def topologicalSort(self):
 
        topological = []
        q = []
 
        # In starting append all node
        # with indegree 0
        for i in range(self.V):
            if (self.indegree[i] == 0):
                q.append(i)
 
        while (len(q) != 0):
            t = q[0]
            q.pop(0)
 
            # Append the node into topological
            # vector
            topological.append(t)
 
            # Reducing indegree of adjacent
            # vertices
            for j in self.adj[t]:
                self.indegree[j] -= 1
 
                # If indegree becomes 0, just
                # append into queue
                if (self.indegree[j] == 0):
                    q.append(j)
 
        return topological
 
    # The function prints all edges that
    # can be added without making any cycle
    # It uses recursive topologicalSort()
    def maximumEdgeAddtion(self):
 
        visited = [False for i in range(self.V)]
 
        topo = self.topologicalSort()
 
        # Looping for all nodes
        for i in range(len(topo)):
            t = topo[i]
 
            # In below loop we mark the
            # adjacent node of t
            for j in self.adj[t]:
                visited[j] = True
 
            # In below loop unmarked nodes
            # are printed
            for j in range(i + 1, len(topo)):
 
                # If not marked, then we can make
                # an edge between t and j
                if (not visited[topo[j]]):
                    print(str(t) + '-' +
                          str(topo[j]), end=' ')
 
                visited[topo[j]] = False
 
 
# Driver code
if __name__ == '__main__':
 
    # Create a graph given in the
    # above diagram
    g = Graph(6)
    g.addEdge(5, 2)
    g.addEdge(5, 0)
    g.addEdge(4, 0)
    g.addEdge(4, 1)
    g.addEdge(2, 3)
    g.addEdge(3, 1)
 
    g.maximumEdgeAddtion()
 
# This code is contributed by rutvik_56

// C# program to find maximum edges after Adding
// which graph still remains a DAG
 
using System;
using System.Collections.Generic;
 
public class Graph {
    private int V; // No. of vertices
 
    private List<int>[] adj; // adjacency list
 
    // array to store indegree of vertices
    private int[] indegree;
 
    // Constructor of graph
    public Graph(int v)
    {
        V = v;
        indegree = new int[V];
        adj = new List<int>[ V ];
        for (int i = 0; i < V; i++) {
            adj[i] = new List<int>();
            indegree[i] = 0;
        }
    }
 
    // Utility function to Add edge
    public void AddEdge(int v, int w)
    {
        adj[v].Add(w); // Add w to v's list.
 
        // increasing inner degree of w by 1
        indegree[w]++;
    }
 
    // function to print maximum edges that can be Added
    public List<int> TopologicalSort()
    {
 
        List<int> topological = new List<int>();
        Queue<int> q = new Queue<int>();
 
        // In starting push all node with indegree 0
        for (int i = 0; i < V; i++) {
            if (indegree[i] == 0) {
                q.Enqueue(i);
            }
        }
 
        while (q.Count > 0) {
            int t = q.Dequeue();
 
            // push the node into topological list
            topological.Add(t);
 
            // reducing inDegree of adjacent vertical
            foreach(int j in adj[t])
            {
                indegree[j]--;
 
                // if inDegree becomes 0, just push
                // into queue
                if (indegree[j] == 0) {
                    q.Enqueue(j);
                }
            }
        }
 
        return topological;
    }
 
    // The function prints all edges that can be
    // Added without making any cycle
    // It uses recursive topologicalSort()
    public void MaximumEdgeAddtion()
    {
        bool[] visited = new bool[V];
        List<int> topo = TopologicalSort();
 
        // looping for all nodes
        for (int i = 0; i < topo.Count; i++) {
            int t = topo[i];
 
            // In below loop we mark the adjacent node of t
            foreach(int j in adj[t]) { visited[j] = true; }
 
            for (int j = i + 1; j < topo.Count; j++) {
                // if not marked, then we can make an edge
                // between t and j
                if (!visited[topo[j]]) {
                    Console.Write(t + "-" + topo[j] + " ");
                }
 
                visited[topo[j]] = false;
            }
        }
        Console.WriteLine();
    }
 
    // Driver code to test above methods
    static void Main(string[] args)
    {
 
        // Create a graph given in the above diagram
        Graph g = new Graph(6);
        g.AddEdge(5, 2);
        g.AddEdge(5, 0);
        g.AddEdge(4, 0);
        g.AddEdge(4, 1);
        g.AddEdge(2, 3);
        g.AddEdge(3, 1);
 
        g.MaximumEdgeAddtion();
    }
}
 
// This code is contributed by cavi4762.

4-5 4-2 4-3 5-3 5-1 2-0 2-1 0-3 0-1 

Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.