旅行商(TSP)

Description

Shrek is a postman working in the mountain, whose routine work is sending mail to n villages. Unfortunately, road between villages is out of repair for long time, such that some road is one-way road. There are even some villages that can’t be reached from any other village. In such a case, we only hope as many villages can receive mails as possible.

Shrek hopes to choose a village A as starting point (He will be air-dropped to this location), then pass by as many villages as possible. Finally, Shrek will arrived at village B. In the travelling PRocess, each villages is only passed by once. You should help Shrek to design the travel route.

Input

There are 2 integers, n and m, in first line. Stand for number of village and number of road respectively.

In the following m line, m road is given by identity of villages on two terminals. From v1 to v2. The identity of village is in range [1, n].

Output

Output maximum number of villages Shrek can pass by.

Example

Input

4 31 42 44 3
Output
3
Restrictions
1 <= n <= 1,000,000
0 <= m <= 1,000,000
These is no loop road in the input.
Time: 2 sec
Memory: 256 MB
Hints
Topological sorting
描述
Shrek是一個大山里的郵遞員，每天負責給所在地區(qū)的n個村莊派發(fā)信件。但杯具的是，由于道路狹窄，年久失修，村莊間的道路都只能單向通過，甚至有些村莊無法從任意一個村莊到達。這樣我們只能希望盡可能多的村莊可以收到投遞的信件。
Shrek希望知道如何選定一個村莊A作為起點（我們將他空投到該村莊），依次經(jīng)過盡可能多的村莊，路途中的每個村莊都經(jīng)過僅一次，最終到達終點村莊B，完成整個送信過程。這個任務交給你來完成。
輸入
第一行包括兩個整數(shù)n，m，分別表示村莊的個數(shù)以及可以通行的道路的數(shù)目。
以下共m行，每行用兩個整數(shù)v1和v2表示一條道路，兩個整數(shù)分別為道路連接的村莊號，道路的方向為從v1至v2，n個村莊編號為[1, n]。
輸出
輸出一個數(shù)字，表示符合條件的最長道路經(jīng)過的村莊數(shù)。
樣例
見英文題面
限制
1 ≤ n ≤ 1,000,000
0 ≤ m ≤ 1,000,000
輸入保證道路之間沒有形成環(huán)
時間：2 sec
空間：256 MB
提示
拓撲排序
本來做這題是毫無思路的，后來看到了題下的提示說要用拓撲排序
然后思路就清晰了許多，寫完debug了半天才想起來這OJ無法使用
C++容器，于是乖乖查了題解。
具體算法仍是拓撲排序的傳統(tǒng)做法：
找到入度為0的點作為起點，依次處理后繼，
唯一的不同是需要保存到達該城市的當前最大值。
然后更新答案即可
#include<stdio.h>using namespace std;#define maxn 1000005int MAX(int a,int b){	if(a<b)		return b;	return a;}int n,m,cnt,q[maxn],degree[maxn];//q為拓撲數(shù)組---cnt為其長度//degree為各點入度//n,m分別為點數(shù)和邊數(shù)int ans=1;//保存答案struct node{	int num;//村莊編號	node *next;	node()	{		next=NULL;	}	node(int x,node *n) :num(x),next(n){}};//該OJ無法使用C++容器，因此//只能現(xiàn)學自認為重定義（看了題解）struct city{	node *nc;//next-city	int dp;//至此所通過的最大城市數(shù)	city(){nc=NULL;dp=1;}	void insert(int nc);}a[maxn];void city::insert(int nc){	degree[nc]++;	if(this->nc==NULL)		this->nc=new node(nc,NULL);	else	{		node *nodes=new node(nc,this->nc);		this->nc=nodes;	}	return;}void Topology(){	for(int i=1;i<=n;i++)		if(!degree[i])			q[++cnt]=i;	for(int i=1;q[i];i++)	{		int res=q[i];		for(node *tmp=a[res].nc;tmp!=NULL;tmp=tmp->next)		{			a[tmp->num].dp=MAX(a[res].dp+1,a[tmp->num].dp);			ans=MAX(ans,a[tmp->num].dp);			//處理后繼			int x=tmp->num;			degree[x]--;			if(!degree[x])				q[++cnt]=x;		}	}}int  main(){	scanf("%d%d",&n,&m);	for(int i=0;i<m;i++)	{		int x,y;		scanf("%d%d",&x,&y);		a[x].insert(y);	}	Topology();	printf("%d/n",ans);}