strongly_connected_components.hpp¶
返回按拓扑序排列的强连通分量列表，分量内点号递增；直接用原边表建立 CSR，递归 Tarjan 返回 low 值，省去中间边表复制与独立 low 数组。
Complexity: Time: \(O(V + E)\). Space: \(O(V + E)\).
AC 记录：scc。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(V + E).
/// Space: O(V + E).
#include "atcoder/internal_csr.hpp"
#include <algorithm>
#include <cassert>
#include <limits>
#include <utility>
#include <vector>
namespace noya {
/// @brief Decompose a directed graph into strongly connected components in
/// topological order; vertices within each component are increasing.
/// Empty graphs, loops and parallel edges are allowed. Require 0<=n<INT_MAX,
/// valid endpoints and at most INT_MAX edges. Input is unchanged. Preserve
/// ACL's traversal-dependent order between incomparable components.
/// Recursive Tarjan may use O(n) call depth; local tests use 512 MiB stacks.
inline std::vector<std::vector<int>>
strongly_connected_components(int n,
const std::vector<std::pair<int, int>> &es) {
assert(0 <= n && n < std::numeric_limits<int>::max());
assert(es.size() <= std::size_t(std::numeric_limits<int>::max()));
for (auto [u, v] : es) {
assert(0 <= u && u < n && 0 <= v && v < n);
}
std::vector<int> ids(n);
int count = 0;
{ // Release traversal storage before constructing the component vectors.
atcoder::internal::csr<int> g(n, es);
std::vector<int> stack, ord(n, -1);
stack.reserve(n);
int now = 0;
auto dfs = [&](auto &self, int v) -> int {
int low = ord[v] = now++;
stack.push_back(v);
for (int i = g.start[v]; i < g.start[v + 1]; ++i) {
int u = g.elist[i];
low = std::min(low, ord[u] == -1 ? self(self, u) : ord[u]);
}
if (low == ord[v]) {
while (true) {
int u = stack.back();
stack.pop_back();
ord[u] = n; // Completed components no longer lower an active low-link.
ids[u] = count;
if (u == v) break;
}
++count;
}
return low;
};
for (int v = 0; v < n; ++v)
if (ord[v] == -1) dfs(dfs, v);
}
std::vector<int> sizes(count);
for (auto &id : ids) {
id = count - 1 - id;
++sizes[id];
}
std::vector<std::vector<int>> result(count);
for (int id = 0; id < count; ++id) result[id].reserve(sizes[id]);
for (int v = 0; v < n; ++v) result[ids[v]].push_back(v);
return result;
}
} // namespace noya
// NOYA_STRONGLY_CONNECTED_COMPONENTS_HPP
#ifndef NOYA_STRONGLY_CONNECTED_COMPONENTS_HPP
#define NOYA_STRONGLY_CONNECTED_COMPONENTS_HPP 1
/// @complexity Time: O(V + E).
/// Space: O(V + E).
#include "atcoder/internal_csr.hpp"
#include <algorithm>
#include <cassert>
#include <limits>
#include <utility>
#include <vector>
namespace noya {
/// @brief Decompose a directed graph into strongly connected components in
/// topological order; vertices within each component are increasing.
/// Empty graphs, loops and parallel edges are allowed. Require 0<=n<INT_MAX,
/// valid endpoints and at most INT_MAX edges. Input is unchanged. Preserve
/// ACL's traversal-dependent order between incomparable components.
/// Recursive Tarjan may use O(n) call depth; local tests use 512 MiB stacks.
inline std::vector<std::vector<int>>
strongly_connected_components(int n,
const std::vector<std::pair<int, int>> &es) {
assert(0 <= n && n < std::numeric_limits<int>::max());
assert(es.size() <= std::size_t(std::numeric_limits<int>::max()));
for (auto [u, v] : es) {
assert(0 <= u && u < n && 0 <= v && v < n);
}
std::vector<int> ids(n);
int count = 0;
{ // Release traversal storage before constructing the component vectors.
atcoder::internal::csr<int> g(n, es);
std::vector<int> stack, ord(n, -1);
stack.reserve(n);
int now = 0;
auto dfs = [&](auto &self, int v) -> int {
int low = ord[v] = now++;
stack.push_back(v);
for (int i = g.start[v]; i < g.start[v + 1]; ++i) {
int u = g.elist[i];
low = std::min(low, ord[u] == -1 ? self(self, u) : ord[u]);
}
if (low == ord[v]) {
while (true) {
int u = stack.back();
stack.pop_back();
ord[u] = n; // Completed components no longer lower an active low-link.
ids[u] = count;
if (u == v) break;
}
++count;
}
return low;
};
for (int v = 0; v < n; ++v)
if (ord[v] == -1) dfs(dfs, v);
}
std::vector<int> sizes(count);
for (auto &id : ids) {
id = count - 1 - id;
++sizes[id];
}
std::vector<std::vector<int>> result(count);
for (int id = 0; id < count; ++id) result[id].reserve(sizes[id]);
for (int v = 0; v < n; ++v) result[ids[v]].push_back(v);
return result;
}
} // namespace noya
#endif // NOYA_STRONGLY_CONNECTED_COMPONENTS_HPP
/// @complexity Time: O(V + E).
/// Space: O(V + E).
#include <algorithm>
#include <utility>
#include <vector>
namespace atcoder {
namespace internal {
template <class E> struct csr {
std::vector<int> start;
std::vector<E> elist;
explicit csr(int n, const std::vector<std::pair<int, E>>& edges)
: start(n + 1), elist(edges.size()) {
for (auto e : edges) {
start[e.first + 1]++;
}
for (int i = 1; i <= n; i++) {
start[i] += start[i - 1];
}
auto counter = start;
for (auto e : edges) {
elist[counter[e.first]++] = e.second;
}
}
};
} // namespace internal
} // namespace atcoder
#include <algorithm>
#include <cassert>
#include <limits>
#include <utility>
#include <vector>
namespace noya {
/// @brief Decompose a directed graph into strongly connected components in
/// topological order; vertices within each component are increasing.
/// Empty graphs, loops and parallel edges are allowed. Require 0<=n<INT_MAX,
/// valid endpoints and at most INT_MAX edges. Input is unchanged. Preserve
/// ACL's traversal-dependent order between incomparable components.
/// Recursive Tarjan may use O(n) call depth; local tests use 512 MiB stacks.
inline std::vector<std::vector<int>>
strongly_connected_components(int n,
const std::vector<std::pair<int, int>> &es) {
assert(0 <= n && n < std::numeric_limits<int>::max());
assert(es.size() <= std::size_t(std::numeric_limits<int>::max()));
for (auto [u, v] : es) {
assert(0 <= u && u < n && 0 <= v && v < n);
}
std::vector<int> ids(n);
int count = 0;
{ // Release traversal storage before constructing the component vectors.
atcoder::internal::csr<int> g(n, es);
std::vector<int> stack, ord(n, -1);
stack.reserve(n);
int now = 0;
auto dfs = [&](auto &self, int v) -> int {
int low = ord[v] = now++;
stack.push_back(v);
for (int i = g.start[v]; i < g.start[v + 1]; ++i) {
int u = g.elist[i];
low = std::min(low, ord[u] == -1 ? self(self, u) : ord[u]);
}
if (low == ord[v]) {
while (true) {
int u = stack.back();
stack.pop_back();
ord[u] = n; // Completed components no longer lower an active low-link.
ids[u] = count;
if (u == v) break;
}
++count;
}
return low;
};
for (int v = 0; v < n; ++v)
if (ord[v] == -1) dfs(dfs, v);
}
std::vector<int> sizes(count);
for (auto &id : ids) {
id = count - 1 - id;
++sizes[id];
}
std::vector<std::vector<int>> result(count);
for (int id = 0; id < count; ++id) result[id].reserve(sizes[id]);
for (int v = 0; v < n; ++v) result[ids[v]].push_back(v);
return result;
}
} // namespace noya
// NOYA_STRONGLY_CONNECTED_COMPONENTS_HPP