学步园

经典问题，没什么好说的。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;

const int maxn = 1000 + 10;
vector<int> g[maxn], g1[maxn];
int n, m;
int pre[maxn], lowlink[maxn], sccno[maxn], dfs_clock, scc_cnt;
int scc_num[maxn], top[maxn], vis[maxn], dp[maxn], cnt;
stack<int> s;

void prework()
{
    memset(pre, 0, sizeof(pre));
    memset(lowlink, 0, sizeof(lowlink));
    memset(sccno, 0, sizeof(sccno));
    memset(vis, 0, sizeof(vis));
    dfs_clock = scc_cnt = 0;
    cnt = 1;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i) { g[i].clear(); g1[i].clear(); }
    while(!s.empty()) s.pop();
    for(int i = 0; i < m; ++i)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        g[a].push_back(b);
    }
}

void dfs(int u)
{
    pre[u] = lowlink[u] = ++dfs_clock;
    s.push(u);
    for(int i = 0; i < g[u].size(); ++i)
    {
        int v = g[u][i];
        if(!pre[v])
        {
            dfs(v);
            lowlink[u] = min(lowlink[u], lowlink[v]);
        }
        else if(!sccno[v])
        {
            lowlink[u] = min(lowlink[u], pre[v]);
        }
    }
    if(lowlink[u] == pre[u])
    {
        scc_cnt++;
        scc_num[scc_cnt] = 0;
        while(1)
        {
            int x = s.top(); s.pop();
            sccno[x] = scc_cnt;
            scc_num[scc_cnt]++;
            if(x == u) break;
        }
    }
}

void dfs1(int u)
{
    vis[u] = 1;
    for(int i = 0; i < g1[u].size(); ++i)
    {
        int v = g1[u][i];
        if(!vis[v]) dfs1(v);
    }
    top[cnt++] = u;
}

void slove()
{
    for(int i = 1; i <= n; ++i)
        if(!pre[i]) dfs(i);
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 0; j < g[i].size(); ++j)
        {
            int v = g[i][j];
            if(sccno[i] != sccno[v])
                g1[sccno[i]].push_back(sccno[v]);
        }
    }
    for(int i = 1; i <= scc_cnt; ++i)
        if(!vis[i]) dfs1(i);
    for(int i = 1; i <= scc_cnt; ++i)
    {
        int u = top[i];
        dp[u] = scc_num[u];
        for(int j = 0; j < g1[u].size(); ++j)
        {
            int v = g1[u][j];
            dp[u] = max(dp[u], scc_num[u] + dp[v]);
        }
    }
    int ans = 0;
    for(int i = 1; i <= scc_cnt; ++i)
        ans = max(ans, dp[i]);
    printf("%d\n", ans);
}

int main()
{
    freopen("in.txt", "r", stdin);
    int t; cin >> t;
    while(t--)
    {
        prework();
        slove();
    }
    return 0;
}