Codeforces round 660 Problem D

 Problem Statement Link: https://codeforces.com/problemset/problem/1388/D

First of all, we can consider the update operations between some two elements of the array as a directed edge going from current one to the updating one. So, now it has become a graph problem.

For the additional condition given in the input format section, our graph will be a directed acyclic graph (DAG). Now, we can easily see that it will be most profitable to go deeper from a current node when we have performed the operations for each of those nodes which has an edge to the current node.

So, we will start from a node which has indegree 0. Before that we will calculate the topological sort order for our graph. We know that in DAG, if there is a directed edge from some node u to other node v, then u will definitely come before v in the topological sort order.

Now it is okay to run dfs in the topological sort order. While going, deeper we will carry the sum of all previous a[v] in current dfs. We will also push the nodes in a vector as an answer and update the maximum answer by adding this sum. 

If somewhere inside the dfs, the sum for current dfs nodes becomes negative, then we will stop going deeper and also won’t push the current node to the answer vector. We will push such nodes after all those dfs are run and will push them in the reverse of topological sort order.

My solution code:

#include<bits/stdc++.h> #define ll long long #define pb push_back using namespace std; int n; ll a[200005]; ll ta[200005]; int b[200005]; vector<int>adj[200005],topsort; int vis[200005]; int vis2[200005]; int indegree[200005]; void input(); void tdfs(int v){     vis[v]++;     for(int i=0;i<adj[v].size();i++){         int u = adj[v][i];         if(vis[u]==0)tdfs(u);     }     topsort.pb(v); } ll ans; vector<int>nodes; void dfs(int v, ll total){     vis2[v]++;     ta[v] = total;     if(total<0)return;     nodes.pb(v);     for(int i=0;i<adj[v].size();i++){         int u = adj[v][i];         indegree[u]--;         a[u] += ta[v];         if(vis2[u]==0 and total+a[u]>=0 and indegree[u]==0)dfs(u,a[u]);     } } void solve(){     for(int i=1;i<=n;i++){         if(b[i]!=-1)adj[i].pb(b[i]);     }     for(int i=1;i<=n;i++){         if(vis[i]==0)tdfs(i);     }     reverse(topsort.begin(),topsort.end());     for(int i=0;i<n;i++){         int v = topsort[i];         if(vis2[v]==0)dfs(v,a[v]);     }     for(int i=n-1;i>=0;i--){         int u = topsort[i];         ans+=ta[u];         if(ta[u]<0)nodes.pb(u);     }     cout<<ans<<"\n";     for(int i=0;i<n;i++){         cout<<nodes[i];         if(i<n-1)cout<<" ";     }     cout<<"\n"; } void Clear(){ } int main(){     ios::sync_with_stdio(false);     //cin.tie(0);     input();     solve();     Clear(); } void input(){     cin>>n;     for(int i=1;i<=n;i++){         ll x;         cin>>x;         a[i] = x;     }     for(int i=1;i<=n;i++){         int x;         cin>>x;         b[i] = x;         if(x!=-1)indegree[x]++;     } }

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

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