本文共 983 字，大约阅读时间需要 3 分钟。

旅行计划

题目描述

小明要去一个国家旅游。这个国家有#NN个城市，编号为11至NN，并且有MM条道路连接着，小明准备从其中一个城市出发，并只往东走到城市i停止。

所以他就需要选择最先到达的城市，并制定一条路线以城市i为终点，使得线路上除了第一个城市，每个城市都在路线前一个城市东面，并且满足这个前提下还希望游览的城市尽量多。

现在，你只知道每一条道路所连接的两个城市的相对位置关系，但并不知道所有城市具体的位置。现在对于所有的i，都需要你为小明制定一条路线，并求出以城市ii为终点最多能够游览多少个城市。

输入格式

第11行为两个正整数N, MN,M。

接下来MM行，每行两个正整数x, yx,y，表示了有一条连接城市xx与城市yy的道路，保证了城市xx在城市yy西面。

输出格式

NN行，第ii行包含一个正整数，表示以第ii个城市为终点最多能游览多少个城市。

输入输出样例

输入 #1

5 61 21 32 32 43 42 5

输出 #1

12343

解题思路

BFS+拓扑

#include
   
    #include
    
     #include
     
      using namespace std;int n,m,tot,head[100010],maxx[100010],maxn,f[100010];int a[100010],b[100010],ok;struct abc{   	int to,next;}s[200010];void add(int x,int y){   	s[++tot]=(abc){   y,head[x]};	head[x]=tot;}void bfs(){   	int tl=0,hd=0;	for(int i=1;i<=n;i++)		if(b[i]==0)		{   			tl++;			f[tl]=i;		}	if(tl==0)	{   		cout<<-1<
      
       >n>>m;	for(int i=1;i<=m;i++)	{   		int x,y;		scanf("%d%d",&x,&y);		add(x,y);		b[y]++;	}	bfs();	if(!ok)		for(int i=1;i<=n;i++)			cout<
       
        <