#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<int> pre[100050];
int dp[100500];
void init() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++) {
int a, b;
scanf("%d %d", &a, &b);
pre[b].push_back(a);
}
}
int dfs(int x, int y) {
if (dp[x]) return 0;
dp[x] = max(dp[x], y);
for (int i = 0; i < pre[x].size(); i++) {
dfs(pre[x][i], y);
}
}
void solve() {
for (int i = n; i >= 1; i--) {
dfs(i, i);
}
for (int i = 1; i <= n; i++) {
cout<<dp[i]<<" ";
}
}
int main() {
init();
solve();
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<int> pre[100050];
int dp[100500];
void init() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++) {
int a, b;
scanf("%d %d", &a, &b);
pre[b].push_back(a);
}
}
void dfs(int x, int y) {//仅此处与前处不同
if (dp[x]) return;//仅此处与前处不同
dp[x] = max(dp[x], y);
for (int i = 0; i < pre[x].size(); i++) {
dfs(pre[x][i], y);
}
}
void solve() {
for (int i = n; i >= 1; i--) {
dfs(i, i);
}
for (int i = 1; i <= n; i++) {
cout<<dp[i]<<" ";
}
}
int main() {
init();
solve();
return 0;
}
这两份代码的唯一区别就是一个的dfs有返回值而另一个没有,然鹅如果将有返回值的那份代码喂给评测姬则会直接全RE爆0, 但是没有返回值的却完美AC 实在疑惑,求大佬们解答QAQ