QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#371457#999. 边双连通分量IsrothyWA 99ms26792kbC++232.4kb2024-03-30 12:42:572024-03-30 12:42:59

Judging History

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

  • [2024-03-30 12:42:59]
  • 评测
  • 测评结果:WA
  • 用时:99ms
  • 内存:26792kb
  • [2024-03-30 12:42:57]
  • 提交

answer

#include <cstdio>
#include <optional>
#include <span>
#include <vector>
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

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3792kb

input:

4 5
0 2
0 1
3 0
2 1
2 3

output:

1
4 0 2 1 3

result:

ok OK

Test #2:

score: 0
Accepted
time: 0ms
memory: 4076kb

input:

13 21
4 5
8 7
12 3
3 10
1 5
10 2
0 0
11 4
2 12
9 1
9 0
7 8
7 6
9 1
8 2
12 10
11 0
8 6
3 2
5 9
4 11

output:

3
6 0 9 11 1 5 4
4 2 10 12 3
3 6 7 8

result:

ok OK

Test #3:

score: 0
Accepted
time: 0ms
memory: 4072kb

input:

2 2
0 1
1 0

output:

1
2 0 1

result:

ok OK

Test #4:

score: -100
Wrong Answer
time: 99ms
memory: 26792kb

input:

200000 200000
127668 148778
77100 11865
85144 199231
39485 84917
102044 187263
130204 174776
26220 198288
162188 12078
92196 146334
120537 38083
150353 160479
18707 6545
101149 25450
62271 9177
38892 6454
11709 191939
89247 145109
140599 121858
197410 148980
55975 169098
128576 59852
68224 182347
89...

output:

105340
1 0
94660 1 196297 9259 81390 89202 199857 78223 152391 122336 78748 111501 158266 24036 32932 8316 1190 163544 22352 133465 61251 154506 26312 73742 26893 51025 109513 105960 117898 104884 196087 56255 163996 89186 77981 33913 187272 111924 163058 10423 70690 174526 87370 148347 112830 14052...

result:

wrong answer tecc is differ