题意:
给n个点m条有向边。求出满足这个条件的最小集合数量:该集合内任意两个点相互之间不能直接或间接到达。也就是说 这个集合内的任意两个点都没有关系。
输出满足这个条件的最小集合数

思路:
首先将强连通分量缩点。该缩点的点权为点的个数。因为强连通分量中任意两个点都有直接或者间接关系。
缩点后重新建图。
然后对新图拓扑排序求最长链。
拓扑排序的三个步骤(队列实现):
1)将入度为0的点放入队列中
2)从队列中取出点,将其边指向的下一个点的入度-1
3)重复1)、2)的步骤直到队列为空

//author: CHC
//First Edit Time: 2014-07-07 15:27
//Last Edit Time: 2014-07-07 15:27
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
#define MAXN 100010
vector <int> e[MAXN];
vector <int> e1[MAXN];
int dfn[MAXN],low[MAXN],bleg[MAXN],sta[MAXN];
int times,top,n,m;
void tarjan(int u){
dfn[u]=low[u]=++times;
sta[++top]=u;
for(int i=0;i<(int)e[u].size();i++){
int v=e[u][i];
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(!bleg[v])
low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
bleg[0]++;
do {
bleg[sta[top]]=bleg[0];
} while (sta[top--]!=u);
}
}
void init(){
memset(dfn,0,sizeof(dfn));
memset(bleg,0,sizeof(bleg));
top=times=0;
}
int vis[MAXN];
int vv[MAXN];
int ru[MAXN];
queue <int> q;
int bfs(){
while(!q.empty())q.pop();
for(int i=1;i<=bleg[0];i++){
if(ru[i]==0){
q.push(i);
vis[i]=vv[i];
}
else vis[i]=0;
}
int mm=0;
while(!q.empty()){
int now=q.front();
q.pop();
if(vis[now]>mm)mm=vis[now];
for(int i=0;i<(int)e1[now].size();i++){
int next=e1[now][i];
vis[next]=max(vis[next],vis[now]+vv[next]);
ru[next]--;
if(ru[next]==0)
q.push(next);
}
}
return mm;
}
int main()
{
while(~scanf("%d%d",&n,&m)){
for(int i=0;i<n+10;i++)e[i].clear();
for(int i=0;i<n+10;i++)e1[i].clear();
for(int i=0;i<n+10;i++)vv[i]=0;
for(int i=0;i<m;i++){
int x,y;
scanf("%d%d",&x,&y);
e[x].push_back(y);
}
init();
for(int i=1;i<=n;i++)
if(!dfn[i])tarjan(i);
memset(ru,0,sizeof(ru));
for(int i=1;i<=n;i++){
++vv[bleg[i]];
for(int j=0;j<(int)e[i].size();j++){
int v=e[i][j];
if(bleg[i]==bleg[v])continue;
e1[bleg[i]].push_back(bleg[v]);
++ru[bleg[v]];
}
}
printf("%d\n",bfs());
}
return 0;
}