目录
题目描述
小明要去一个国家旅游。这个国家有#N个城市,编号为1至N,并且有M条道路连接着,小明准备从其中一个城市出发,并只往东走到城市i停止。
所以他就需要选择最先到达的城市,并制定一条路线以城市i为终点,使得线路上除了第一个城市,每个城市都在路线前一个城市东面,并且满足这个前提下还希望游览的城市尽量多。
现在,你只知道每一条道路所连接的两个城市的相对位置关系,但并不知道所有城市具体的位置。现在对于所有的i,都需要你为小明制定一条路线,并求出以城市ii为终点最多能够游览多少个城市。
输入格式
第11行为两个正整数N,M。
接下来MM行,每行两个正整数x,y,表示了有一条连接城市x与城市y的道路,保证了城市x在城市y西面。
输出格式
N行,第i行包含一个正整数,表示以第i个城市为终点最多能游览多少个城市。
输入输出样例
输入 #1
5 6 1 2 1 3 2 3 2 4 3 4 2 5
输出 #1
1 2 3 4 3
说明/提示
均选择从城市1出发可以得到以上答案。
对于20%的数据,N≤100;
对于60%的数据,N≤1000;
对于100%的数据,N≤100000,M≤200000。
图片解释
这就是图,简单easy as a pai
1 2 一在二左
1 3 一在三左
2 3 二在二左
2 4 二在四左
3 4 三在四左
2 5 二在五左
开头点1 结尾点2
开头点1 结尾点3
开头点1 结尾点4
开头点1 结尾点5
// |------------------|
#include<iostream>// |--头文件,头文件--|
#include<cstdio>// |--头文件,头文件--|
#include<algorithm>// |--头文件,头文件--|
#include<cmath>// |--头文件,头文件--|
#include<cstring>// |--头文件,头文件--|
#include<queue>// |--头文件,头文件--|
// |------------------|
using namespace std;//定义命名空间
struct EDGE//定义结构体
{
int next;//下一位
int to;//前一位
}edge[200005];//存每一个点
int n,m,sum,tot;//n,m和两个计数变量
int head[200005],ru[200005],ts[200005],dp[200005];//数组下面讲
void add(int x,int y)//把数据添加近 edge
{
edge[++sum].next=head[x];//这一位的上一位是x头
edge[sum].to=y;//下一位是y
head[x]=sum;//x头=sum
}
void topsort()//拓扑排序
{
queue<int>q;//定义队列
for(int i=1;i<=n;i++)//寻找第一个入读为0的点
{
if(ru[i]==0)//找到
{
q.push(i);//压入队列
ts[++tot]=i;//记录顺序
}
}
while(!q.empty())//如果不为空
{
int tmp=q.front();//记录头
q.pop();//弹出
for(int j=head[tmp];j;j=edge[j].next)//从头开始,往next找,如果不用结构体,就要从1开始找,用结构体节省时间
{
int v=edge[j].to;//记录下一位
ru[v]--;//删除边
if(ru[v]==0)//如果有新的入读为0的点
{
q.push(v);//压入队列
ts[++tot]=v;//记录顺序
}
}
}
}
int main()
{
cin>>n>>m;//输入点和边
for(int i=1;i<=m;i++)
{
int x,y;//输入边的开始位置
cin>>x>>y;//开头和结尾
add(x,y);//在函数中讲
ru[y]++;//统计入读
}
topsort();//拓扑排序
for(int i=1;i<=n;i++)
{
dp[i]=1;//初始化
}
//一下为动态规划//
for(int i=1;i<=n;i++)
{
int t=ts[i];//记录拓扑排序顺序
for(int j=head[t];j;j=edge[j].next)//从头开始,往next找,如果不用结构体,就要从1开始找,用结构体节省时间
{
int v=edge[j].to;//记录下一位
dp[v]=max(dp[i],dp[t]+1);
}
}
/*
仔细看DP部分,还记得DP需要满足什么原则吗?无后效性。
如果不是在拓扑序中进行DP,会完全破坏无后效性(当然这
也下面为什么有人用记忆化搜索的原因,记忆化搜索同样可
以解决无后效性的问题)。正是因为拓扑序u在前,v在后的
性质,这才选择使用拓扑排序,毕竟它的代码实现很轻松,
而且运行时间也不差。
至于怎么求拓扑序,就是把入度为0(就是没有边把它作为
终点)的点入队,并加入拓扑序。之后断掉以这个点为起点
的边,即将这些边的终点的入度减一,直到队为空就好。
*/
for(int i=1;i<=n;i++)//输出
{
cout<<dp[i]<<endl;
}
}