DAG and Topsort order

 ধরে নেই, আমাদেরকে একটি DAG (Directed Acyclic Graph)  দেওয়া হয়েছে। এই DAG এর কোন দুইটি node u এবং v এর মধ্যে একটি directed node আছে যেটি u থেকে v এর দিকে।

এখন আমরা যদি এই DAG এর সকল নোডের topsort এর order বিবেচনা করি তবে দেখব যে u নোডটি v নোডের আগে আসবে। এভাবে ওই DAG এর সকল directed edge এর জন্য এটি সত্য হবে। আরেকটু ভালোভাবে খেয়াল করলে দেখব, যদি কোন node u থেকে অন্য একটি node v তে যাওয়া গেলে topsort এর order এ node u অবশ্যই node v এর আগে আসবে। এই idea অনেক problem solving এ কাজে দেয়। 

এখন আমরা এই idea ব্যবহার করে একটি problem solve করব। এটি codeforces round 656 এর problem E (Link : https://codeforces.com/contest/1385/problem/E ).

এই problem এ আমাদেরকে একটি গ্রাফ দেওয়া হবে যেখানে directed এবং undirected দুই ধরনের edge ই থাকেবে। আমাদেরকে এই গ্রাফের undirected edge গুলোকে directed করে একটি DAG বানাতে হবে । আর যদি DAG বানানো সম্ভব না হয় তাহলে সেটা বলতে হবে। 

Solution idea: আমরা গ্রাফটির উপর dfs চালিয়ে প্রথমে নোডগুলোর topsort order বের করব। এরপর আমরা গ্রাফের প্রতিটি directed edge এর জন্য এটি check করব যে, যদি node u থেকে node v তে edge থাকে, তবে topsort এর order এ node u, node v এর আগে এসেছে কিনা। যদি কোন directed edge এর জন্য এটি সত্য না হয়, তাহলে গ্রাফটির জন্য কোন answer নেই। কারণ directed acyclic graph এ কোন node u থেকে অন্য কোন node v তে যাওয়া গেলে অবশ্যই topsort এর order এ node u , node v এর আগে থাকবে। 

অন্যথায় গ্রাফটির জন্য answer থাকবে। এক্ষেত্রে আমরা প্রতিটি undirected edge এর জন্য দুইটি নোডের মধ্যে যেটি topsort এর order এ আগে আছে, সেটি থেকে অপরটিতে একটি directed edge দিবো। 

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}]++;         }     } }