Maximum edges that can be added to DAG so that is remains DAG in C ++

In this article, we will discuss Maximum edges that can be added to DAG so that remains DAG in C ++. You are given a directed acyclic graph(DAG)  and you have to find the maximum edges you can add so that the remaining graph will also be directed acyclic.

At first, let’s quickly understand with an example-

In the above graph, if you add some particular edges, the remaining graph will also be directed acyclic(DAG). Those edges are-0->4 , 0->2 , 0->5 , 3->1 , 3->5 , 4->1 , 4->2 , 1->5

Now let’s discuss the algorithm:
At first, get the topological sort of the graph in an array. Then traverse the array from beginning. While traversing, if you find any element from the rest of the array is not adjacent to that element, then add an edge. That’s how you can find all the edges. That’s the tricky part of the solution. But for the solution, you have to know about topological sorting. If you don’t know then go through this link- Topological Sort in C++.

Now quickly see the implementation-

#include<bits/stdc++.h>
using namespace std;

//function for adding edge
void add(int v,int w,vector<int>graph[]){
    graph[v].push_back(w);
}

//bfs traversal fot getting topological sorted order
void bfs(vector<int>graph[],int i,vector<bool>&vis,stack<int>&s){
    vis[i]=true;
    for(auto v:graph[i]){
        if(!vis[v])
            bfs(graph,v,vis,s);
    }
    s.push(i);
}

//get the topological sort and build the array
vector<int>topologicalSort(vector<int>graph[],int V){
    stack<int>s;
    vector<bool>vis(V,false);
    for(int i=0;i<V;i++){
        if(!vis[i])
            bfs(graph,i,vis,s);
    }
    vector<int>temp(V);
    int i=0;
    while(!s.empty()){
        temp[i++]=s.top();
        s.pop();
    }
    return temp;
    
}


void getMaximumEdges(vector<int>graph[],int V){
    vector<int>temp=topologicalSort(graph,V);
    vector<bool>vis(V,false);
    for (int i = 0; i < temp.size(); i++) //traversing the topological sorted array
    { 
        int t = temp[i]; 
        for (auto j = graph[t].begin(); j != graph[t].end(); j++) 
            vis[*j] = true; 
        for (int j = i + 1; j < temp.size(); j++) //see the rest array for finding edges
        { 
            if (!vis[temp[j]]) //if the element is not adjacent then add edge
                cout << t << "->" << temp[j] << " "; 
  
            vis[temp[j]] = false; 
        } 
    } 
}


int main(){
//build the graph
    int V=6;
    vector<int>graph[V];
    add(0, 1,graph); 
    add(0, 3,graph); 
    add(1, 2,graph); 
    add(3, 2,graph); 
    add(2, 5,graph); 
    add(3, 4,graph);
    add(4, 5,graph);

    getMaximumEdges(graph,V);

    return 0;
}

Output:
0->4 0->2 0->5 3->1 3->5 4->1 4->2 1->5