题目描述
小埋最近在学习有向图的遍历相关知识，小埋学习过图的遍历的相关方法，可以使用 DFS 或者 BFS 来遍历整个有向图，但是小埋发现这个问题有一些不一样，这个图的遍历是问你当前点能够到达的点的最大编号，小埋希望你能帮她解决这个问题。
输入格式
第一行两个整数 n 和 m，n 代表有向图中有 n 个点，m 代表有向图中有 m 条有向边。
接下来是 m 条边。
输出格式
输出每个点能够到达的最大编号
样例
Input 1
4 3 1 2 1 3 2 3
Output 1
3 3 3 4
样例解释
样例1解释：
从1开始，可以到达的最大编号是3；
从2开始，可以到达的最大编号是3；
从3开始，可以到达的最大编号是3；
从4开始，可以到达的最大编号是4。
数据范围
数据范围：1<=n,m<=100000
思路：广搜+反向建图
#include<bits/stdc++.h>
using namespace std;
int n,m,u,v,rem;
vector<int> a[100005];
bool vis[100005];
int ans[100005];
void print(){
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
return;
}
void bfs(int x){
if(ans[x]==0){
ans[x]=x;
rem--;
if(rem==0){
print();
exit(0);
}
}
for(int i=0;i<a[x].size();i++){
if(vis[a[x][i]]) continue;
vis[a[x][i]]=true;
if(ans[a[x][i]]==0){
ans[a[x][i]]=x;
rem--;
if(rem==0){
print();
exit(0);
}
}
bfs(a[x][i]);
}
return;
}
int main(){
scanf("%d%d",&n,&m);
rem=n;
for(int i=1;i<=m;i++){
scanf("%d%d",&u,&v);
a[v].push_back(u);
}
for(int i=n;i>=1;i--) bfs(i);
return 0;
}