### YGBoss007's blog

By YGBoss007, history, 3 years ago,

Your text to link here... My logic is as follows: First of all, we can get all the SCC's of the graph with their respective sums. Now we can make a condensed graph sort of thing, where each SCC acts as a node. I'm not able to get what to do after that? I gave a hard thought of maintaining DP after that but couldn't get on with the recurrence relations. Any help would be appreciated.

• +3

 » 3 years ago, # |   0 As you might have guessed that if we add SCC to our final result, the whole value of that SCC will get added. Further, what we can now do is for each SCC, we find out how many other SCC's it can visit. Here we will call a DFS so that only once we add a particular node value to its corresponding DP. That would mean dp[i] = sum of dp[adjacent nodes from i] + current node value DFS will take care that you don't add a value multiple times.
•  » » 4 months ago, # ^ |   0 can you share implementation for this logic ?
 » 2 months ago, # |   0 #pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx,avx2,fma") #include using namespace std; #define int long long #define float long double #define fast_io ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); const int MOD = 1e9 + 7; const int INF = 1e17 + 7; void topoSort(int u, stack &topo, vector &vis, vector> &adj) { vis[u] = true; for(int v: adj[u]) { if(!vis[v]) { topoSort(v, topo, vis, adj); } } topo.push(u); } void dfsInv(int u, int cnt, vector &scc, vector &vis, vector> &adj) { vis[u] = true; scc[u] = cnt; for(int v: adj[u]) { if(!vis[v]) { dfsInv(v, cnt, scc, vis, adj); } } } int dfsMeta(int u, vector &vis, vector> &adj, vector &dp) { int res = 0; vis[u] = true; for(int v: adj[u]) { if(vis[v]) { res = max(res, dp[v]); } else { res = max(res, dfsMeta(v, vis, adj, dp)); } } return dp[u] += res; } void solve() { int n, m; cin >> n >> m; vector k(n); for(int &i: k) { cin >> i; } vector> adj(n), inv(n); for(int i = 0; i < m; i++) { int a, b; cin >> a >> b; adj[a - 1].push_back(b - 1); inv[b - 1].push_back(a - 1); } //Kosaraju's Algorithm vector vis(n, false); stack topo; for(int u = 0; u < n; u++) { if(!vis[u]) { topoSort(u, topo, vis, adj); } } vector scc(n, 0); vis = vector(n, false); int cnt = 0; while(!topo.empty()) { int node = topo.top(); topo.pop(); if(!vis[node]) { dfsInv(node, cnt, scc, vis, inv); cnt++; } } //Build the meta graph (the graph of SCCs) vector> meta(cnt); vector dp(cnt, 0); vector visMeta(cnt, vector(cnt, false)); for(int u = 0; u < n; u++) { dp[scc[u]] += k[u]; for(int v: adj[u]) { if(scc[u] != scc[v] && !visMeta[scc[u]][scc[v]]) { visMeta[scc[u]][scc[v]] = true; meta[scc[u]].push_back(scc[v]); } } } //Do dp on the meta graph to get the optimal answer vis = vector(cnt, false); int res = 0; for(int u = 0; u < cnt; u++) { if(!vis[u]) { res = max(res, dfsMeta(u, vis, meta, dp)); } } cout << res << endl; } signed main() { fast_io #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif solve(); }