Gym - 101170B British Menu SCC点数目不超过5的最长路

题意其实就是给你一个有向图 但是每个SCC里面的点数目不超过5 求最长路

首先暴力把每个SCC里的每个点的最长路跑出来 然后拓扑排序dp

#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long ll;
const int N = 1000005;
vector<int> g[2 * N], g2[N];
int dfn[N], low[N], bel[N], dfc, scc;
bool inst[N];
int scs[N], *sct = scs;
void scc_clr(int n) {
        fill(dfn + 1, dfn + n + 1, 0);
}
int dfs_scc(int u) {
        *sct++ = u;
        inst[u] = 1;
        dfn[u] = low[u] = ++dfc;
        for (int v : g[u]) {
                if (!dfn[v]) {
                        low[u] = min(low[u], dfs_scc(v));
                } else if (inst[v]) {
                        low[u] = min(low[u], dfn[v]);
                }
        }
        if (dfn[u] == low[u])
                for (++scc; *sct != u; --sct) {
                        bel[sct[-1]] = scc, inst[sct[-1]] = 0;
                }
        return low[u];
}
bool vis[N];
int dp[N], du[N];
int ans = 0;
queue<int> que;
int doit(int x, int y, bool f) {
        if (vis[x]) {
                return 0;
        }
        if (bel[x] != y) {
                if (f) {
                        return dp[x];
                } else {
                        return 0;
                }
        }
        int anser = 1;
        vis[x] = 1;
        for (int v : g[x]) {
                anser = max(anser, doit(v, y, f) + 1);
        }
        vis[x] = 0;
        dp[x] = max(dp[x], anser);
        ans = max(ans, dp[x]);
        return anser;
}
int main () {
        int n, m;
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= m; i++) {
                int u, v;
                scanf("%d %d", &u, &v);
                g[u].push_back(v);
        }
        for (int i = 1; i <= n; i++)
                if (!dfn[i]) {
                        dfs_scc(i);
                }
        for (int i = 1; i <= n; i++) {
                g[bel[i] + n].push_back(i);
                for (int v : g[i]) {
                        if (bel[v] != bel[i]) {
                                g2[bel[v]].push_back(bel[i]);
                                du[bel[i]]++;
                        }
                }
        }
        for (int i = 1; i <= scc; i++) {
                if (du[i] == 0) {
                        que.push(i);
                }
                for (int v : g[i + n]) {
                        doit(v, i, 0);
                }
        }
        while (que.size()) {
                int x = que.front();
                que.pop();
                for (int v : g[x + n]) {
                        doit(v, x, 1);
                }
                for (int v : g2[x]) {
                        du[v]--;
                        if (du[v] == 0) {
                                que.push(v);
                        }
                }
        }
        cout << ans << endl;
}