ZOJ 3795：Grouping（缩点+最长路）

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5303

题意：有n个人m条边，每条边有一个u，v，代表u的年龄大于等于v，现在要将这n个人分成x个组，组内的人的年龄不能够直接或者间接比较，问最少可以分成多少组。

思路：一开始没看清题意，直接拓扑排序做了。后来听师兄说会有环，年龄大于等于，如果有环代表这里面的年龄相等，那么环里面的人都是每个人一组，缩完点之后那个点的长度就是点的人数，然后用DP最长路做。

 #include <cstdio>

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <string>

 #include <cmath>

 #include <queue>

 #include <vector>

 #include <map>

 #include <set>

 #include <stack>

 using namespace std;

 #define INF 0x3f3f3f3f

 #define N 100010

 struct Edge {

     int v, nxt;

 } edge[N*], edg[N*];

 int cnt[N], dp[N], head[N], hea[N], tott, tot, tim, vis[N], deg[N], dfn[N], low[N], belong[N], num;

 stack<int> sta;

 void Add(int u, int v) {

     edge[tot].v = v; edge[tot].nxt = head[u]; head[u] = tot++;

 }

 void add(int u, int v) {

     edg[tott].v = v; edg[tott].nxt = hea[u]; hea[u] = tott++;

 }

 void tarjan(int u) {

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

     sta.push(u); vis[u] = ;

     for(int i = head[u]; ~i; i = edge[i].nxt) {

         Edge &e = edge[i];

         if(!dfn[e.v]) {

             tarjan(e.v);

             if(low[e.v] < low[u]) low[u] = low[e.v];

         } else if(vis[e.v] && dfn[e.v] < low[u]) low[u] = dfn[e.v];

     }

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

         ++num; int v = -;

         cnt[num] = ;

         while(v != u) {

             v = sta.top(); sta.pop();

             belong[v] = num;

             cnt[num]++;

             vis[v] = ;

         }

     }

 }

 int DFS(int u) {

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

     int ans = cnt[u];

     for(int i = hea[u]; ~i; i = edg[i].nxt) {

         int v = edg[i].v;

         ans = max(ans, DFS(v) + cnt[u]);

     }

     return dp[u] = ans;

 }

 int main() {

     int n, m;

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

         memset(head, -, sizeof(head));

         memset(hea, -, sizeof(hea));

         memset(dfn, , sizeof(dfn));

         memset(dp, , sizeof(dp));

         tot = num = tott = tim = ;

         int u, v;

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

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

             Add(u, v);

         }

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

             if(!dfn[i]) tarjan(i);

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

             for(int i = head[u]; ~i; i = edge[i].nxt) {

                 int v = edge[i].v;

                 if(belong[u] != belong[v]) {

                     add(belong[u], belong[v]);

                 }

             }

         }

         int ans = ;

         for(int i = ; i <= num; i++)

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

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

     }

     return ;

 }