QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#357912 | #906. 强连通分量 | Isrothy | WA | 418ms | 70136kb | C++23 | 2.6kb | 2024-03-19 14:54:35 | 2024-03-19 14:54:37 |
Judging History
answer
#include <cstdio>
#include <queue>
#include <span>
#include <stack>
#include <vector>
struct TarjanScc {
std::vector<std::vector<size_t>> adj, sccs;
std::vector<size_t> dfn, low;
std::stack<size_t> stk;
std::vector<bool> on_stack;
size_t dfs_clock;
TarjanScc(std::span<std::pair<size_t, size_t>> edges, size_t n)
: adj(n), dfn(n), low(n), on_stack(n), dfs_clock(0) {
for (auto [u, v]: edges) {
adj[u].emplace_back(v);
}
for (size_t u = 0; u < n; ++u) {
if (!dfn[u]) {
find_sccs(u);
}
}
}
private:
void find_sccs(size_t u) {
dfn[u] = low[u] = ++dfs_clock;
stk.push(u);
on_stack[u] = true;
for (auto v: adj[u]) {
if (!dfn[v]) {
find_sccs(v);
low[u] = std::min(low[u], low[v]);
} else if (on_stack[v]) {
low[u] = std::min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
std::vector<size_t> scc;
while (true) {
auto v = stk.top();
stk.pop();
on_stack[v] = false;
scc.push_back(v);
if (v == u) {
break;
}
}
sccs.emplace_back(std::move(scc));
}
}
};
int main() {
size_t n, m;
scanf("%zd%zd", &n, &m);
std::vector<std::pair<size_t, size_t>> edges(m);
for (auto &[u, v]: edges) {
scanf("%zu%zu", &u, &v);
}
auto sccs = TarjanScc(edges, n).sccs;
std::vector<std::vector<size_t>> adj(sccs.size());
std::vector<size_t> degree(sccs.size(), 0), sccno(n, -1);
for (size_t i = 0; i < sccs.size(); ++i) {
for (auto u: sccs[i]) {
sccno[u] = i;
}
}
for (const auto &[u, v]: edges) {
if (auto x = sccno[u], y = sccno[v]; sccno[x] != sccno[y]) {
adj[x].push_back(y);
++degree[y];
}
}
std::queue<size_t> q;
for (size_t i = 0; i < sccs.size(); ++i) {
if (!degree[i]) {
q.push(i);
}
}
printf("%zu\n", sccs.size());
while (!q.empty()) {
auto u = q.front();
q.pop();
printf("%zu ", sccs[u].size());
for (auto x: sccs[u]) {
printf("%zu ", x);
}
puts("");
for (auto v: adj[u]) {
--degree[v];
if (!degree[v]) {
q.push(v);
}
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3788kb
input:
6 7 1 4 5 2 3 0 5 5 4 1 0 3 4 2
output:
4 2 3 0 2 4 1 1 5 1 2
result:
ok OK
Test #2:
score: -100
Wrong Answer
time: 418ms
memory: 70136kb
input:
500000 500000 389812 410922 255712 339244 274009 248522 347288 199231 235313 301629 469588 84917 364188 449407 392348 436920 26220 198288 162188 468965 274222 92196 463222 408478 231663 467768 382681 38083 412497 160479 280851 268689 101149 25450 62271 9177 38892 268598 273853 250782 191939 89247 40...
output:
499590 1 3 1 4 1 5 1 6 1 7 1 10 1 13 1 14 1 17 1 19 1 20 1 21 1 24 1 25 1 26 1 27 1 31 1 32 1 34 1 37 1 39 1 42 1 43 1 46 1 47 1 59 1 60 1 67 1 68 1 76 1 80 1 85 1 86 1 88 1 89 1 94 1 107 1 111 1 113 1 114 1 119 1 120 1 121 1 123 1 129 1 130 1 132 1 133...
result:
wrong answer 101960 is later than 294822, but there is an edge (101960, 294822)