QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#369532 | #995. 桥 | Isrothy | Compile Error | / | / | C++23 | 2.3kb | 2024-03-28 13:50:10 | 2024-03-28 13:50:11 |
Judging History
This is the latest submission verdict.
- [2024-03-28 13:50:11]
- Judged
- Verdict: Compile Error
- Time: 0ms
- Memory: 0kb
- [2024-03-28 13:50:10]
- Submitted
answer
#include <optional>
#include <span>
#include <vector>
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;
}
详细
answer.code: In function ‘int main()’: answer.code:62:5: error: ‘scanf’ was not declared in this scope 62 | scanf("%d %d", &n, &m); | ^~~~~ answer.code:70:13: error: ‘printf’ was not declared in this scope 70 | printf("%lu %lu\n", edges[i].first, edges[i].second); | ^~~~~~ answer.code:4:1: note: ‘printf’ is defined in header ‘<cstdio>’; did you forget to ‘#include <cstdio>’? 3 | #include <vector> +++ |+#include <cstdio> 4 | struct TarjanEcc {