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