QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#371457 | #999. 边双连通分量 | Isrothy | WA | 99ms | 26792kb | C++23 | 2.4kb | 2024-03-30 12:42:57 | 2024-03-30 12:42:59 |
Judging History
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