题目链接：https://cn.vjudge.net/problem/ZOJ-3795

题目大意：给你n个人，m个关系， 让你对这个n个人进行分组，要求：尽可能的分组最少，然后每个组里面的人都没有关系。

具体思路：首先对年龄相同的人进行缩点，这些人是肯定不能在同一个组里面的。然后缩完点之后找出剩下的图中一条最长路（每个点的权值就是缩完点之后当前联通块里面的人的个数），我们找出最长路之后（最长路通过拓扑排序判断），这就是答案了。即使有别的图中的人，我们都可以放进这个最长链形成的分组个数中。

AC代码：

  1 #include<iostream>
  2 #include<stdio.h>
  3 #include<cmath>
  4 #include<algorithm>
  5 #include<cstring>
  6 #include<algorithm>
  7 #include<queue>
  8 #include<stack>
  9 using namespace std;
 10 # define ll long long
 11 # define inf 0x3f3f3f3f
 12 const int maxn = 2e5+100;
 13 int n,m,num,ord,col;
 14 int head[maxn],low[maxn],dfn[maxn];
 15 int cont[maxn],in[maxn];
 16 int istack[maxn],dp[maxn];
 17 struct node
 18 {
 19     int fr;
 20     int to;
 21     int nex;
 22 } edge[maxn<<2];
 23 vector<int>Map[maxn];
 24 stack<int>q;
 25 void init()
 26 {
 27     num=0;
 28     ord=0;
 29     col=0;
 30     while(!q.empty())
 31         q.pop();
 32     for(int i=0; i<=n; i++)
 33     {
 34         head[i]=-1;
 35         low[i]=0;
 36         dfn[i]=0;
 37         cont[i]=0;
 38         in[i]=0;
 39         istack[i]=0;
 40         dp[i]=0;
 41     }
 42 }
 43 void addedge(int fr,int to)
 44 {
 45     edge[num].fr=fr;
 46     edge[num].to=to;
 47     edge[num].nex=head[fr];
 48     head[fr]=num++;
 49 }
 50 void dfs(int u)
 51 {
 52     low[u]=dfn[u]=++ord;
 53     q.push(u);
 54     for(int i=head[u]; i!=-1; i=edge[i].nex)
 55     {
 56         int to=edge[i].to;
 57         if(dfn[to]==0)
 58         {
 59             dfs(to);
 60             low[u]=min(low[u],low[to]);
 61         }
 62         else if(istack[to]==0)
 63         {
 64             low[u]=min(low[u],dfn[to]);
 65         }
 66     }
 67     if(low[u]==dfn[u])
 68     {
 69         int t;
 70         col++;
 71         do
 72         {
 73             t=q.top();
 74             q.pop();
 75             istack[t]=col;
 76             cont[col]++;
 77         }
 78         while(t!=u);
 79     }
 80 }
 81 void tarjan()
 82 {
 83     for(int i=1; i<=n; i++)
 84     {
 85         if(!dfn[i])
 86             dfs(i);
 87     }
 88 }
 89 void topsort()
 90 {
 91     while(!q.empty())
 92         q.pop();
 93     for(int i=1; i<=col; i++)
 94     {
 95         if(!in[i])
 96             q.push(i);
 97         dp[i]=cont[i];
 98     }
 99     while(!q.empty())
100     {
101         int top=q.top();
102         q.pop();
103         for(int i=0; i<Map[top].size(); i++)
104         {
105             int to=Map[top][i];
106             dp[to]=max(dp[to],dp[top]+cont[to]);
107             if(--in[to]==0)
108             {
109                 q.push(to);
110             }
111         }
112     }
113 }
114 int main()
115 {
116     while(~scanf("%d %d",&n,&m)){
117         init();
118         int st,ed;
119         for(int i=1; i<=m; i++)
120         {
121             scanf("%d %d",&st,&ed);
122             addedge(st,ed);
123         }
124         tarjan();
125         for(int i=0; i<=col; i++)
126         {
127             Map[i].clear();
128         }
129         for(int i=0; i<num; i++)//注意这个地方要重新建图。
130         {
131             if(istack[edge[i].fr]!=istack[edge[i].to])
132             {
133                 Map[istack[edge[i].fr]].push_back(istack[edge[i].to]);
134                 in[istack[edge[i].to]]++;
135             }
136         }
137         topsort();
138         int maxx=0;
139         for(int i=1; i<=col; i++)
140         {
141             maxx=max(maxx,dp[i]);
142         }
143         printf("%d\n",maxx);
144     }
145     return 0;
146 }