社区讨论

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 条回复,欢迎继续交流。

正在加载回复...