题目传送门:https://www.luogu.com.cn/problem/P3916
解法一:DFS
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
typedef pair<int, int> pii;
constexpr int N = 1e5 + 5, M = 1e5 + 5;
int ver[M], nxt[M], head[N], tot, vis[N], d[N];
void add(int x, int y) {
ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
}
void dfs(int x, int val) {
if (vis[x]) return;
vis[x] = 1;
d[x] = val;
for (int i = head[x]; i ; i = nxt[i]) {
int y = ver[i];
dfs(y, val);
}
}
void solve()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int x, y;
cin >> x >> y;
add(y, x);
}
for (int i = n; i >= 1; --i) {
dfs(i, i);
}
for (int i = 1; i <= n; ++i) {
cout << d[i] << ' ';
}
}
int main()
{
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
2025年8月5日大约 1 分钟