3040: 【普及/提高-】【P3916】图的遍历
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：2
题目描述
给出 个点， 条边的有向图，对于每个点 ，求 表示从点 出发，能到达的编号最大的点。
输入
第 行 个整数 ，表示点数和边数。
接下来 行，每行 个整数 ，表示边 。点用 编号。
输出
一行 个整数 。
样例输入 复制
4 3
1 2
2 4
4 3样例输出 复制
4 4 3 4提示
- 对于 的数据，。
- 对于 的数据，。
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
int n,m;
vector <int> p[MAXN];
int a[MAXN];
void solve (int x,int v) {
a[x] = v; //将点x的答案更新为v
for (int i = 0; i < p[x].size(); i++)
if (a[p[x][i]] == 0) //如果答案没有被更新过，则用当前点的值更新
solve(p[x][i],v);
}
int main(){
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u,v;
cin >> u >> v;
p[v].push_back(u); //建反向边
}
for (int i = n; i >= 0; i--)
if (a[i] == 0)
solve(i,i);
for (int i = 1; i <= n; i++)
cout << a[i] << ' ';
return 0;
}