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.
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 maximum number of villages Shrek can pass by.
Input
4 31 42 44 3Output
3Restrictions
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是一個(gè)大山里的郵遞員，每天負(fù)責(zé)給所在地區(qū)的n個(gè)村莊派發(fā)信件。但杯具的是，由于道路狹窄，年久失修，村莊間的道路都只能單向通過，甚至有些村莊無法從任意一個(gè)村莊到達(dá)。這樣我們只能希望盡可能多的村莊可以收到投遞的信件。
Shrek希望知道如何選定一個(gè)村莊A作為起點(diǎn)（我們將他空投到該村莊），依次經(jīng)過盡可能多的村莊，路途中的每個(gè)村莊都經(jīng)過僅一次，最終到達(dá)終點(diǎn)村莊B，完成整個(gè)送信過程。這個(gè)任務(wù)交給你來完成。
輸入
第一行包括兩個(gè)整數(shù)n，m，分別表示村莊的個(gè)數(shù)以及可以通行的道路的數(shù)目。
以下共m行，每行用兩個(gè)整數(shù)v1和v2表示一條道路，兩個(gè)整數(shù)分別為道路連接的村莊號，道路的方向?yàn)閺膙1至v2，n個(gè)村莊編號為[1, n]。
輸出
輸出一個(gè)數(shù)字，表示符合條件的最長道路經(jīng)過的村莊數(shù)。
樣例
見英文題面
限制
1 ≤ n ≤ 1,000,000
0 ≤ m ≤ 1,000,000
輸入保證道路之間沒有形成環(huán)
時(shí)間：2 sec
空間：256 MB
提示
拓?fù)渑判?/p>
本來做這題是毫無思路的，后來看到了題下的提示說要用拓?fù)渑判?/p>
然后思路就清晰了許多，寫完debug了半天才想起來這OJ無法使用
C++容器，于是乖乖查了題解。
具體算法仍是拓?fù)渑判虻膫鹘y(tǒng)做法：
找到入度為0的點(diǎn)作為起點(diǎn)，依次處理后繼，
唯一的不同是需要保存到達(dá)該城市的當(dāng)前最大值。
然后更新答案即可
#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為拓?fù)鋽?shù)組---cnt為其長度//degree為各點(diǎn)入度//n,m分別為點(diǎn)數(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)學(xué)自認(rè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);}
新聞熱點(diǎn)
疑難解答
