QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#357939#995. 桥IsrothyCompile Error//C++232.3kb2024-03-19 15:23:072024-03-19 15:23:09

Judging History

你现在查看的是最新测评结果

  • [2024-03-19 15:23:09]
  • 评测
  • [2024-03-19 15:23:07]
  • 提交

answer

#include <optional>
#include <span>
struct TarjanEcc {
    std::vector<std::vector<std::pair<size_t, size_t>>> adj;
    std::vector<size_t> dfn, low;
    std::vector<bool> is_bridge;
    std::vector<std::vector<size_t>> eccs;
    size_t dfs_clock;
    TarjanEcc(std::span<std::pair<size_t, size_t>> edges, size_t n)
        : adj(n), dfn(n), low(n), is_bridge(edges.size(), false), eccs(), dfs_clock(0) {
        for (size_t i = 0; i < edges.size(); ++i) {
            auto [u, v] = edges[i];
            adj[u].emplace_back(v, i);
            adj[v].emplace_back(u, i);
        }
        for (size_t u = 0; u < n; ++u) {
            if (!dfn[u]) {
                find_bridges(u, std::nullopt);
            }
        }
        std::vector<bool> visited(n);
        for (size_t u = 0; u < n; ++u) {
            if (!visited[u]) {
                std::vector<size_t> q;
                q.emplace_back(u);
                visited[u] = true;
                for (size_t ptr = 0; ptr < q.size(); ++ptr) {
                    auto v = q[ptr];
                    for (auto [w, id]: adj[v]) {
                        if (!is_bridge[id] && !visited[w]) {
                            visited[w] = true;
                            q.push_back(w);
                        }
                    }
                }
                eccs.emplace_back(std::move(q));
            }
        }
    }

private:
    void find_bridges(size_t u, std::optional<size_t> prev) {
        dfn[u] = low[u] = ++dfs_clock;
        for (auto [v, id]: adj[u]) {
            if (prev == id) {
                continue;
            }
            if (!dfn[v]) {
                find_bridges(v, id);
                low[u] = std::min(low[u], low[v]);
                is_bridge[id] = dfn[u] < low[v];
            } else {
                low[u] = std::min(low[u], dfn[v]);
            }
        }
    }
};

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    std::vector<std::pair<size_t, size_t>> edges(m);
    for (auto &[u, v]: edges) {
        scanf("%zu %zu", &u, &v);
    }
    TarjanEcc ecc(edges, n + 1);
    for (size_t i = 0; i < m; ++i) {
        if (ecc.is_bridge[i]) {
            printf("%lu %lu\n", edges[i].first, edges[i].second);
        }
    }
    return 0;
}

Details

answer.code:4:10: error: ‘vector’ in namespace ‘std’ does not name a template type
    4 |     std::vector<std::vector<std::pair<size_t, size_t>>> adj;
      |          ^~~~~~
answer.code:3:1: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’?
    2 | #include <span>
  +++ |+#include <vector>
    3 | struct TarjanEcc {
answer.code:5:10: error: ‘vector’ in namespace ‘std’ does not name a template type
    5 |     std::vector<size_t> dfn, low;
      |          ^~~~~~
answer.code:5:5: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’?
    5 |     std::vector<size_t> dfn, low;
      |     ^~~
answer.code:6:10: error: ‘vector’ in namespace ‘std’ does not name a template type
    6 |     std::vector<bool> is_bridge;
      |          ^~~~~~
answer.code:6:5: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’?
    6 |     std::vector<bool> is_bridge;
      |     ^~~
answer.code:7:10: error: ‘vector’ in namespace ‘std’ does not name a template type
    7 |     std::vector<std::vector<size_t>> eccs;
      |          ^~~~~~
answer.code:7:5: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’?
    7 |     std::vector<std::vector<size_t>> eccs;
      |     ^~~
answer.code: In constructor ‘TarjanEcc::TarjanEcc(std::span<std::pair<long unsigned int, long unsigned int> >, size_t)’:
answer.code:10:11: error: class ‘TarjanEcc’ does not have any field named ‘adj’
   10 |         : adj(n), dfn(n), low(n), is_bridge(edges.size(), false), eccs(), dfs_clock(0) {
      |           ^~~
answer.code:10:19: error: class ‘TarjanEcc’ does not have any field named ‘dfn’
   10 |         : adj(n), dfn(n), low(n), is_bridge(edges.size(), false), eccs(), dfs_clock(0) {
      |                   ^~~
answer.code:10:27: error: class ‘TarjanEcc’ does not have any field named ‘low’
   10 |         : adj(n), dfn(n), low(n), is_bridge(edges.size(), false), eccs(), dfs_clock(0) {
      |                           ^~~
answer.code:10:35: error: class ‘TarjanEcc’ does not have any field named ‘is_bridge’
   10 |         : adj(n), dfn(n), low(n), is_bridge(edges.size(), false), eccs(), dfs_clock(0) {
      |                                   ^~~~~~~~~
answer.code:10:67: error: class ‘TarjanEcc’ does not have any field named ‘eccs’
   10 |         : adj(n), dfn(n), low(n), is_bridge(edges.size(), false), eccs(), dfs_clock(0) {
      |                                                                   ^~~~
answer.code:13:13: error: ‘adj’ was not declared in this scope
   13 |             adj[u].emplace_back(v, i);
      |             ^~~
answer.code:17:18: error: ‘dfn’ was not declared in this scope
   17 |             if (!dfn[u]) {
      |                  ^~~
answer.code:21:14: error: ‘vector’ is not a member of ‘std’
   21 |         std::vector<bool> visited(n);
      |              ^~~~~~
answer.code:21:14: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’?
answer.code:21:21: error: expected primary-expression before ‘bool’
   21 |         std::vector<bool> visited(n);
      |                     ^~~~
answer.code:23:18: error: ‘visited’ was not declared in this scope
   23 |             if (!visited[u]) {
      |                  ^~~~~~~
answer.code:24:22: error: ‘vector’ is not a member of ‘std’
   24 |                 std::vector<size_t> q;
      |                      ^~~~~~
answer.code:24:22: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’?
answer.code:24:35: error: expected primary-expression before ‘>’ token
   24 |                 std::vector<size_t> q;
      |                                   ^
answer.code:24:37: error: ‘q’ was not declared in this scope
   24 |                 std::vector<size_t> q;
      |                                     ^
answer.code:29:40: error: ‘adj’ was not declared in this scope
   29 |                     for (auto [w, id]: adj[v]) {
      |                                        ^~~
answer.code:30:30: error: ‘is_bridge’ was not declared in this scope; did you mean ‘find_bridges’?
   30 |                         if (!is_bridge[id] && !visited[w]) {
      |                              ^~~~~~~~~
      |                              find_bridges
answer.code:36:17: error: ‘eccs’ was not declared in this scope
   36 |                 eccs.emplace_back(std::move(q));
      |                 ^~~~
answer.code: In member function ‘void TarjanEcc::find_bridges(size_t, std::optional<long unsigned int>)’:
answer.code:43:9: error: ‘dfn’ was not declared in this scope
   43 |         dfn[u] = low[u] = ++dfs_clock;
      |         ^~~
answer.code:43:18: error: ‘low’ was not declared in this scope
   43 |         dfn[u] = low[u] = ++dfs_clock;
      |                  ^~~
answer.code:44:28: error: ‘adj’ was not declared in this scope
   44 |         for (auto [v, id]: adj[u]) {
      |   ...