学步园

水题。给你n个点m条边。入度为0的点标为1，如果一个点只有一个点指向，那么它标为那个点的标数。如果一个点有两个或以上相同标号的点指向。那么给它标为i+1，如果有更大的话就标为更大的。求最大的标号。

拓扑排序

//First Edit Time:	2014-07-15 12:40
//Last Edit Time:	2014-07-15 12:40
//Filename:C.cpp
#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 1010
#define INF_INT 0xfffff0
vector <int> e[MAXN];
int n,m;
int dis[MAXN],cnt[MAXN],pre[MAXN];
int ru[MAXN];
int bfs(){
    queue <int> q;
    for(int i=1;i<=n;i++){
        dis[i]=0;
        pre[i]=-1;
        cnt[i]=0;
        if(ru[i]==0){
            q.push(i);
            cnt[i]=1;
            dis[i]=1;
        }
    }
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(int i=0;i<(int)e[now].size();i++){
            int next=e[now][i];
            if(pre[next]==-1){
                pre[next]=dis[now];
                dis[next]=dis[now];
                cnt[next]=1;
            }
            else{
                if(pre[next]<dis[now]){
                    pre[next]=dis[now];
                    dis[next]=dis[now];
                    cnt[next]=1;
                }
                else if(pre[next]==dis[now]&&cnt[next]==1){
                    if(dis[next]!=dis[now]+1){
                        dis[next]=dis[now]+1;
                    }
                }
            }
            --ru[next];
            if(ru[next]==0){
                q.push(next);
            }
        }
    }
    int mm=dis[1];
    for(int i=2;i<=n;i++)
        if(dis[i]>mm)mm=dis[i];
    /*
    for(int i=1;i<=n;i++){
        printf("%d ",dis[i]);
    }
    puts("");
    */
    return mm;
}
int main()
{
    int t,cas;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&cas);
        scanf("%d%d",&n,&m);
        for(int i=0;i<n+2;i++)e[i].clear();
        memset(ru,0,sizeof(ru));
        for(int i=0,x,y;i<m;i++){
            scanf("%d%d",&x,&y);
            e[x].push_back(y);
            ++ru[y];
        }
        printf("%d %d\n",cas,bfs());
    }
    return 0;
}