社区讨论
这道题这样写为什么不对
题目总版参与者 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 条回复,欢迎继续交流。
正在加载回复...