找宝藏
2024-07-03 16:29:19
发布于:北京
题目描述
小码君被邀请到一个节目上,可以在N个岛上寻找宝藏,会随机给小码君降落到其中的一个岛上,每一个岛有通向其他岛的路径(也有可能没有),都有的岛屿之间一共有M条路径,每一个岛都有一个编号,编号越大的岛屿宝藏价值越大,小码君现在想要知道所有位置可以能够去往的最大的编号的岛屿是多少。
提示
n<1000,m<2000
输入格式
第一行输入一个N,M表示有N个岛,M条路径
输出格式
每一个点可以去往的最大的岛屿的编号
样例组输入#1
5 3
1 2
3 4
2 4
样例组输出#1
4 4 4 4 5
#include<bits/stdc++.h>
using namespace std;
int A[1086][1086],a[1086];int n,m;
bool v[1086];
void ddd(int x,int y){
a[x]=max(a[x],y);v[y]=1;for(int i=1;i<=n;i++){if(A[y][i] && !v[i]){ddd(x,i);}}
}
int main(){
cin>>n>>m;for(int i=1;i<=m;i++){int x,y;cin>>x>>y;A[x][y]=1;}for(int i=1;i<=n;i++){memset(v,0,sizeof v);ddd(i,i);}for(int i=1;i<=n;i++){cout<<a[i]<<' ';}
return 0;
}
这里空空如也
有帮助,赞一个