DAG and Topological Sort Order

 DAG And Topsort

Let's assume, we are given a DAG (Directed Acyclic Graph). In this DAG, let’s consider an edge from some node u to some node v. 

Now, if we consider the topological sort of the nodes of this DAG, then we will see that node u will come before node v in the topological sort order. And this will be a fact for any directed edge u⇾v. If we have a closer look, we will see that if we can go from some node u to some node v with one or multiple edges in the DAG, then node u will come before node v in the topological sort order. This idea is useful in solving some DAG problems.  

We will now solve a problem using this idea. This is problem E from codeforces round 656 (Link : https://codeforces.com/contest/1385/problem/E ).

In this problem, we are given a graph which contains directed and undirected - both types of edges. We have to convert the undirected edges to the directed ones and make a DAG. And if we can’t do so, we will print “NO”.

Solution idea: We will run a dfs on the given graph and find the topological sort order of its nodes. After that, we will check for each directed edge u⇾v if v comes before u. If so, then there will be no solution. Because in DAG, if there is an directed edge from some node u to other node v, then u will definitely come before v in the topological sort order. So, we will print “NO”. 

Otherwise, there will be a solution. In this case, for each undirected edge u⇄v, we will make u⇾v if u comes before v in topological sort order or we will make v⇾u if v comes before u in topological sort order. 

My Solution Code: 

#include<bits/stdc++.h> #define ll long long #define pb push_back using namespace std; int n,m; vector<int>adj[200005]; vector<int>T; vector<pair<int,int> >undir,dir; int vis[200005]; int idx[200005]; map<pair<int,int>,int >edge; void Tdfs(int v){     vis[v]++;     for(int i=0;i<adj[v].size();i++){         int u = adj[v][i];         if(edge[{v,u}]>0 and edge[{u,v}]>0)continue;         if(vis[u]==0)Tdfs(u);     }     T.pb(v); } void input(); void solve(){     for(int i=1;i<=n;i++){         if(vis[i]==0 and (adj[i].size()>0))Tdfs(i);     }     reverse(T.begin(),T.end());     for(int i=0;i<T.size();i++){         idx[T[i]] = i+1;     }     for(int i=0;i<dir.size();i++){         int u = dir[i].first;         int v = dir[i].second;         if(idx[u]>idx[v]){             cout<<"NO\n";             return;         }     }     cout<<"YES\n";     for(int i=0;i<undir.size();i++){         int u = undir[i].first;         int v = undir[i].second;         if(idx[u]<idx[v]){             cout<<u<<" "<<v<<"\n";         }         else{             cout<<v<<" "<<u<<"\n";         }     }     for(int i=0;i<dir.size();i++)cout<<dir[i].first<<" "<<dir[i].second<<"\n"; } void Clear(){     for(int i=0;i<=n;i++){         adj[i].clear();         vis[i] = 0;         idx[i] = 0;     }     T.clear();     undir.clear();     dir.clear();     edge.clear(); } int main(){     ios::sync_with_stdio(false);     cin.tie(0);     int t;     cin>>t;     while(t--){         input();         solve();         Clear();     } } void input(){     cin>>n>>m;     for(int i=0;i<m;i++){         int type;         cin>>type;         int u,v;         cin>>u>>v;         if(type==0){             adj[u].pb(v);   adj[v].pb(u);             undir.pb({u,v});             edge[{u,v}]++;  edge[{v,u}]++;         }         else{             adj[u].pb(v);             dir.pb({u,v});             edge[{u,v}]++;         }     } }