社区讨论
100分求助
P3916图的遍历参与者 4已保存回复 7
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 7 条
- 当前快照
- 1 份
- 快照标识符
- @m26da96c
- 此快照首次捕获于
- 2024/10/13 00:24 去年
- 此快照最后确认于
- 2025/11/04 17:20 4 个月前
CPP
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int n, m;
std::cin >> n >> m;
std::vector<std::vector<int>> adj(n);
for (int i = 0; i < m; ++i) {
int u, v;
std::cin >> u >> v;
--u, --v;
adj[u].push_back(v);
}
std::vector<int> dp(n, -1);
std::iota(dp.begin(), dp.end(), 0);
std::vector<int> vis(n, 0);
auto dfs = [&](auto& self, int x)->void {
if (vis[x]) return;
vis[x] = 1;
for (auto& y : adj[x]) {
self(self, y);
dp[x] = std::max(dp[x], dp[y]);
}
};
for (int k = 0; k < 3; ++k) { // 暴力试出来的, 为什么这里转移三次就能过?
std::fill(vis.begin(), vis.end(), 0);
for (int i = n - 1; i >= 0; --i) {
dfs(dfs, i);
}
}
for (auto& x : dp) std::cout << x + 1 << " ";
std::cout << '\n';
return 0;
}
回复
共 7 条回复,欢迎继续交流。
正在加载回复...