QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#371456#999. 边双连通分量IsrothyCompile Error//C++232.3kb2024-03-30 12:42:342024-03-30 12:42:34

Judging History

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

  • [2024-03-30 12:42:34]
  • 评测
  • [2024-03-30 12:42:34]
  • 提交

answer

#include <optional>
#include <span>
struct TarjanEcc {
    std::vector<std::vector<std::pair<int, int>>> adj;
    std::vector<int> dfn, low;
    std::vector<bool> is_bridge;
    std::vector<std::vector<int>> eccs;
    int dfs_clock;
    TarjanEcc(std::span<std::pair<int, int>> edges, int n)
        : adj(n + 1), dfn(n + 1), low(n + 1), is_bridge(edges.size(), false), eccs(), dfs_clock(0) {
        for (int i = 0; i < edges.size(); ++i) {
            auto [u, v] = edges[i];
            adj[u].emplace_back(v, i);
            adj[v].emplace_back(u, i);
        }
        for (int u = 1; u <= n; ++u) {
            if (!dfn[u]) {
                find_bridges(u, std::nullopt);
            }
        }
        std::vector<bool> visited(n);
        for (int u = 1; u <= n; ++u) {
            if (!visited[u]) {
                std::vector<int> q;
                q.emplace_back(u);
                visited[u] = true;
                for (int 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(int u, std::optional<int> 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<int,int>> edges(m);
    for (auto &[u, v]: edges) {
        scanf("%d%d", &u, &v);
        ++u;
        ++v;
    }
    auto eccs = TarjanEcc(edges, n).eccs;
    printf("%zu\n", eccs.size());
    for (const auto &ecc: eccs) {
        printf("%zu", ecc.size());
        for (auto u: ecc) {
            printf(" %d", u - 1);
        }
        puts("");
    }

    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<int, int>>> 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<int> dfn, low;
      |          ^~~~~~
answer.code:5:5: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’?
    5 |     std::vector<int> 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<int>> eccs;
      |          ^~~~~~
answer.code:7:5: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’?
    7 |     std::vector<std::vector<int>> eccs;
      |     ^~~
answer.code: In constructor ‘TarjanEcc::TarjanEcc(std::span<std::pair<int, int> >, int)’:
answer.code:10:11: error: class ‘TarjanEcc’ does not have any field named ‘adj’
   10 |         : adj(n + 1), dfn(n + 1), low(n + 1), is_bridge(edges.size(), false), eccs(), dfs_clock(0) {
      |           ^~~
answer.code:10:23: error: class ‘TarjanEcc’ does not have any field named ‘dfn’
   10 |         : adj(n + 1), dfn(n + 1), low(n + 1), is_bridge(edges.size(), false), eccs(), dfs_clock(0) {
      |                       ^~~
answer.code:10:35: error: class ‘TarjanEcc’ does not have any field named ‘low’
   10 |         : adj(n + 1), dfn(n + 1), low(n + 1), is_bridge(edges.size(), false), eccs(), dfs_clock(0) {
      |                                   ^~~
answer.code:10:47: error: class ‘TarjanEcc’ does not have any field named ‘is_bridge’
   10 |         : adj(n + 1), dfn(n + 1), low(n + 1), is_bridge(edges.size(), false), eccs(), dfs_clock(0) {
      |                                               ^~~~~~~~~
answer.code:10:79: error: class ‘TarjanEcc’ does not have any field named ‘eccs’
   10 |         : adj(n + 1), dfn(n + 1), low(n + 1), 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<int> q;
      |                      ^~~~~~
answer.code:24:22: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’?
answer.code:24:29: error: expected primary-expression before ‘int’
   24 |                 std::vector<int> q;
      |                             ^~~
answer.code:25:17: error: ‘q’ was not declared in this scope
   25 |                 q.emplace_back(u);
      |                 ^
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(int, std::optional<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]) {
      |           ...