学步园

点击打开链接

有向图

把强联通分量缩点后得到一个DAG，然后DP。

</pre><pre name="code" class="cpp">#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
using namespace std;

const int maxn = 1000 + 10;
vector<int> G[maxn];
int dfn[maxn], low[maxn], sccno[maxn], dfs_clock, scc_cnt;
stack<int> S;

void dfs(int u)
{
    dfn[u] = low[u] = ++dfs_clock;
    S.push(u);
    for(int i=0; i<G[u].size(); ++i) {
        int v = G[u][i];
        if(!dfn[v]) {
            dfs(v);
            low[u] = min(low[u], low[v]);
        } else if(!sccno[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(low[u] == dfn[u]) {
        scc_cnt++;
        for(;;) {
            int x = S.top();
            S.pop();
            sccno[x] = scc_cnt;
            if(x==u) break;
        }
    }
}
void find_scc(int n)
{
    dfs_clock = scc_cnt = 0;
    memset(sccno, 0, sizeof sccno );
    memset(dfn, 0, sizeof dfn );
    for(int i=0; i<n; ++i) {
        if(!dfn[i]) dfs(i);
    }
}

int size[maxn],
    TG[maxn][maxn];//缩点后的SCC图-邻接矩阵
int d[maxn];
int dp(int u)
{
    int & ans = d[u];
    if(ans>=0) return ans;
    ans = size[u];
    for(int v=1; v<=scc_cnt; ++v)
        if(u != v && TG[u][v]) ans=max(ans, dp(v)+size[u]);
    return ans;
}

int main()
{
    int T, n, m;
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &m);
        for(int i=0; i<n; ++i) G[i].clear();
        for(int i=0; i<m; ++i) {
            int u, v;
            scanf("%d%d", &u, &v);
            u--;
            v--;
            G[u].push_back(v);
        }

        find_scc(n);

        memset(TG, 0, sizeof TG );
        memset(size, 0, sizeof size );
        for(int i=0; i<n; ++i) {
            size[sccno[i]]++;
            for(int j=0; j<G[i].size(); ++j)
                TG[sccno[i]][sccno[G[i][j]]] = 1;// 构造SCC图
        }

        int ans = 0;
        memset(d, -1, sizeof d );
        for(int i=1; i<=scc_cnt; ++i) {
            ans = max(ans, dp(i));
        }
        printf("%d\n", ans);
    }
    return 0;
}