社区讨论

这道题这样写为什么不对

题目总版参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lo934ez0
此快照首次捕获于
2023/10/28 04:47
2 年前
此快照最后确认于
2023/10/28 04:47
2 年前
查看原帖
CPP
题目描述 Description
已知某城市有n个公交站编号为1到n,有m条连接两个公交站的公交路线,用xi yi来描述这样一条公交路线,方向为从公交站xi到公交站yi。这m条路线都是有向的,公交车只能按照规定的方向从一个站点到另一个站点,公交路线和公交站点组成了一个有向图,该有向图不会出现环或自环,也不会出现重边。若有了一条从xi到yi的公交路线,则一定不会有从yi到xi的路线。
现给出交通线路的定义:公交车从某个没有上一个站点的公交站出发,经过一条或若干条公交路线到达某一个没有后续站点的公交站结束,所经过路径称为一条交通线路,请问该有向图中有最长的一条交通线路一共有多少个站点。

输入描述 Input Description
第一行两个整数n和m。
接下来m行 每行两个整数xi和yi表示一条xi到yi的公交路线

输出描述 Output Description
一个整数,为站点数量

样例输入 Sample Input
5 7
1 2
1 3
2 3
3 5
2 5
4 5
3 4
样例输出 Sample Output
5
数据范围及提示 Data Size & Hint
n<=5000,m<=500000
CPP
#include <bits/stdc++.h> 
using namespace std;
const int MAXN = 500005;
int n,m,shu[MAXN],in[MAXN],total,f[MAXN];
queue<int>q;
struct node{
	int to,fm;
}e[MAXN];
void Topsort()
{
	for(int i=1;i<=n;i++)
		if(in[i]==0)
		{
			f[i]=1;
			q.push(i);
		}
	while(!q.empty())
	{
		int t=q.front();
		q.pop();
		for(int i=shu[t];i;i=e[i].fm)
		{
			int idx=e[i].to;
			f[idx]=max(f[idx],f[t]+1);
			if(--in[idx]==0)
				q.push(idx);	
		}	
	}
}
int main()
{
	cin >>n >>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin >>x >> y;
		e[++total].to=y;
		e[total].fm=shu[x];
		shu[x]=total;
		in[y]++;
	}
	Topsort();
	int ans=0;
	for(int i=1;i<=n;i++)
		ans = max(ans, f[i]);
	cout << ans <<'\n';
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...