描述

Shrek是一个大山里的邮递员，每天负责给所在地区的n个村庄派发信件。但杯具的是，由于道路狭窄，年久失修，村庄间的道路都只能单向通过，甚至有些村庄无法从任意一个村庄到达。这样我们只能希望尽可能多的村庄可以收到投递的信件。

Shrek希望知道如何选定一个村庄A作为起点（我们将他空投到该村庄），依次经过尽可能多的村庄，路途中的每个村庄都经过仅一次，最终到达终点村庄B，完成整个送信过程。这个任务交给你来完成。

 

 

输入

第一行包括两个整数n，m，分别表示村庄的个数以及可以通行的道路的数目。

以下共m行，每行用两个整数v1和v2表示一条道路，两个整数分别为道路连接的村庄号，道路的方向为从v1至v2，n个村庄编号为[1, n]。

 

 

输出

输出一个数字，表示符合条件的最长道路经过的村庄数。

 

 

输入样例

4 3

1 4

2 4

4 3

 

 

输出样例

3

 

 

限制

1 ≤ n ≤ 1,000,000

0 ≤ m ≤ 1,000,000

输入保证道路之间没有形成环

时间：2 sec

空间：256MB

 

 

 

 

   呜~~我受够了~~~

   一开始用深度遍历，结果只跑了60分，说我慢了~~然后我就开始憋大招，编了一个晚上，用出度的办法一层层剥掉路径树~~然后想着，先放到OJ上看看对不对再剪枝吧~~~结果，结果清华OJ竟然不让用vector ！！！

   简直疯掉了~~从网上找了vector.h打包交上，竟然编译不通过！！！难不成让我自己写几千行的代码？~~一想到我竟然还用到了vector的push_back等函数，就觉得绝望，这要是真写那可就是要写好几个内部的接口函数的啊~~疯掉了~~太晚了~~太打击了~~~我去睡觉了~~

 

   对了，有没有大神来看看我的代码对不对的？

 

 

#include
#include

using namespace std;

vector mgraph;
vector outdegree;
vector length;

int main()
{
   int n,m,v1,v2,i,t;
   cin>>n>>m;
   for(i=0;i    {
       for(t=0;t        {
           mgraph.push_back(0);
       }
       outdegree.push_back(0);
       length.push_back(0);
   }
   //cout<    //cout<<"ok1";
   for(i=0;i    {
       cin>>v1>>v2;
       mgraph[n*v1+v2]=1;
   }
   //cout<<"ok2";

   for(v1=1;v1    {
       t=0;
       for(v2=1;v2        {
           if(mgraph[n*v1+v2]==1) t++;
       }
       outdegree[v1]=t;
   }
   //cout<

   int zero,hight=0;
   vector temp;
   do
   {
       hight++;
       zero=0;
       for(v1=1;v1        {
           if(outdegree[v1]==0 && length[v1]==0)
           {
               zero++;
               length[v1]=hight;//cout<<"v1="<                temp.push_back(v1);//cout<<"temp.capacity()="<            }

 

       }

       for(t=0;t        {
           for(i=1;i            {
               if(mgraph[n*i+temp[t]]==1)
               {
                   mgraph[n*i+temp[t]]=0;outdegree[i]–;
                   //cout<                }
           }
       }
       temp.clear();

       //cout<<"hight="<    }while(zero==1);
   //cout<<"ok5";

   cout<

 

   //cout<    //cout<    return 0;
}