When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

YGBoss007's blog

By YGBoss007, history, 3 years ago, In English

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.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>

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<int> &topo, vector<bool> &vis, vector<vector<int>> &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<int> &scc, vector<bool> &vis, vector<vector<int>> &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<bool> &vis, vector<vector<int>> &adj, vector<int> &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<int> k(n);
    for(int &i: k) {
        cin >> i;
    }

    vector<vector<int>> 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<bool> vis(n, false);
    stack<int> topo;
    for(int u = 0; u < n; u++) {
        if(!vis[u]) {
            topoSort(u, topo, vis, adj);
        }
    }

    vector<int> scc(n, 0);
    vis = vector<bool>(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<vector<int>> meta(cnt);
    vector<int> dp(cnt, 0);
    vector visMeta(cnt, vector<bool>(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<bool>(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();
}