http://acm.sdut.edu.cn:8080/vjudge/contest/view.action?cid=158#problem/F

大致题意：给出n个人和m种关系(ti,si)，表示ti的年龄不小于si。问最小能被划分为几个集合。每一个集合都要满足里面的人都无法比較。

思路：对于一条路上的点。它们必然不能被划分到同一个集合中，因此原题变为求一条最长路。

而题目中有可能出现环。因此，先tarjan缩点转化为DAG，而缩点后的每一个点的点权便是该节点中包括的点的个数。然后记忆化求最长路。

PS：该题与上一篇 

uva 11324 The
Largest Clique是一样的。该题重在转化。

#include <stdio.h>

#include <iostream>

#include <algorithm>

#include <map>

#include <stack>

#include <vector>

#include <math.h>

#include <string.h>

#include <queue>

#include <string>

#include <stdlib.h>

#define LL long long

#define _LL __int64

#define eps 1e-8

#define PI acos(-1.0)

using namespace std;

const int INF = 0x3f3f3f3f;

const int maxn = 100010;

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 u,v;

    while(~scanf("%d %d",&n,&m))

    {

        init();

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

        {

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

            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;

}