http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=25&page=show_problem&problem=2299

题意：输入n和m，有n个点和m条有向边，求出一个节点集合包括的节点个数最多，而且该节点内的不论什么两点a,b，要么a能到达b，要么b能到达a，要么a和b互相到达。

思路：强连通分量缩点形成有向无环图DAG，把缩点后的每一个点的权值置为该强连通分量的节点个数。最后在求DAG上的动态规划。

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <stack>

#include <vector>

#define LL long long

#define _LL __int64

using namespace std;

const int INF = 0x3f3f3f3f;

const int maxn = 1010;

vector <int> edge[maxn],edge2[maxn];

int n,m;

int dfn[maxn],low[maxn],instack[maxn],dep,scc;

stack <int> st;

int set[maxn],num[maxn];

int d[maxn];

void init()

{

    for(int i = 1; i <= n; i++)

    {

        edge[i].clear();

        edge2[i].clear();

    }

    memset(dfn,0,sizeof(dfn));

    memset(low,0,sizeof(low));

    memset(instack,0,sizeof(instack));

    while(!st.empty()) st.pop();

    dep = 0;

    scc = 0;

    memset(num,0,sizeof(num));

    memset(d,0,sizeof(d));

}

void tarjan(int u)

{

    dfn[u] = low[u] = ++dep;

    instack[u] = 1;

    st.push(u);

    for(int i = 0; i < (int)edge[u].size(); i++)

    {

        int v = edge[u][i];

        if(!dfn[v])

        {

            tarjan(v);

            low[u] = min(low[u],low[v]);

        }

        else if(instack[v])

            low[u] = min(low[u],dfn[v]);

    }

    if(dfn[u] == low[u])

    {

        scc++;

        int t;

        while(1)

        {

            t = st.top();

            st.pop();

            instack[t] = 0;

            set[t] = scc;

            num[scc]++;

            if(t == u)

                break;

        }

    }

}

void creat()

{

    for(int u = 1; u <= n; u++)

    {

        for(int i = 0; i < (int)edge[u].size(); i++)

        {

            int v = edge[u][i];

            if(set[u] != set[v])

                edge2[set[u]].push_back(set[v]);

        }

    }

}

int dp(int u)

{

    if(d[u]) return d[u];

    else if(edge2[u].size() == 0) return d[u] = num[u];

    int ans = 0;

    for(int i = 0; i < (int)edge2[u].size(); i++)

    {

        int v = edge2[u][i];

        ans = max(ans,dp(v));

    }

    return d[u] = ans+num[u];

}

int main()

{

    int test,u,v;

    scanf("%d",&test);

    while(test--)

    {

        init();

        scanf("%d %d",&n,&m);

        for(int i = 1; i <= m; i++)

        {

            scanf("%d %d",&u,&v);

            if(u == v) continue;

            edge[u].push_back(v);

        }

        for(int i = 1; i <= n; i++)

            if(!dfn[i])

                tarjan(i);

        creat();

        int ans = 0;

        for(int i = 1; i <= scc; i++)

        {

            ans = max(ans,dp(i));

        }

        printf("%d\n",ans);

    }

    return 0;

}