This documentation is automatically generated by competitive-verifier/competitive-verifier
// @brief Two-Edge-Connected Components
#define PROBLEM "https://judge.yosupo.jp/problem/two_edge_connected_components"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include <iostream>
//#include "blazingio/blazingio.min.hpp"
#include "cp-algo/graph/tarjan.hpp"
#include <bits/stdc++.h>
using namespace std;
using namespace cp_algo::graph;
void solve() {
int n, m;
cin >> n >> m;
graph g(n);
g.read_edges(m);
auto comps = two_edge_connected_components(g);
cout << size(comps) << '\n';
for(auto const& comp: comps.rows()) {
cout << size(comp) << ' ';
for(auto v: comp) {
cout << v << ' ';
}
cout << '\n';
}
}
signed main() {
//freopen("input.txt", "r", stdin);
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
//cin >> t;
while(t--) {
solve();
}
}
#line 1 "verify/graph/2cc.test.cpp"
// @brief Two-Edge-Connected Components
#define PROBLEM "https://judge.yosupo.jp/problem/two_edge_connected_components"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include <iostream>
//#include "blazingio/blazingio.min.hpp"
#line 1 "cp-algo/graph/tarjan.hpp"
#line 1 "cp-algo/graph/dfs_time.hpp"
#line 1 "cp-algo/graph/dfs.hpp"
#line 1 "cp-algo/graph/base.hpp"
#line 1 "cp-algo/graph/edge_types.hpp"
#line 4 "cp-algo/graph/edge_types.hpp"
#include <cstdint>
namespace cp_algo::graph {
using node_index = int;
struct edge_base {
int xor_nodes;
edge_base() {}
edge_base(node_index from, node_index to): xor_nodes(from ^ to) {}
// Given one endpoint, return the other
node_index traverse(node_index from) const {
return xor_nodes ^ from;
}
static auto read(node_index v0 = 0) {
node_index u, v;
std::cin >> u >> v;
u -= v0;
v -= v0;
return std::pair{u, edge_base(u, v)};
}
};
struct weighted_edge: edge_base {
int64_t w;
weighted_edge() {}
weighted_edge(node_index from, node_index to, int64_t w): edge_base(from, to), w(w) {}
static auto read(node_index v0 = 0) {
auto [u, e] = edge_base::read(v0);
int64_t w;
std::cin >> w;
return std::pair{u, weighted_edge(u, e.traverse(u), w)};
}
};
template<typename edge>
concept edge_type = std::is_base_of_v<edge_base, edge>;
template<typename edge>
concept weighted_edge_type = std::is_base_of_v<weighted_edge, edge>;
}
#line 1 "cp-algo/graph/concepts.hpp"
#line 4 "cp-algo/graph/concepts.hpp"
#include <type_traits>
namespace cp_algo::graph {
// Shared graph mode enum for all graph headers
enum graph_mode { directed, undirected };
// Traits: true for types that expose `edge_t` and static `mode`
template<typename T, typename = void>
struct graph_traits : std::false_type {};
template<typename T>
requires requires { typename T::edge_t; T::mode; }
struct graph_traits<T> : std::true_type {
using edge_t = typename T::edge_t;
static constexpr auto mode = T::mode;
static constexpr bool is_directed = mode == directed;
static constexpr bool is_undirected = mode == undirected;
static constexpr bool is_weighted = weighted_edge_type<edge_t>;
};
// Concepts
template<typename G>
concept graph_type = graph_traits<G>::value;
template<typename G>
concept digraph_type = graph_type<G> && graph_traits<G>::is_directed;
template<typename G>
concept undirected_graph_type = graph_type<G> && graph_traits<G>::is_undirected;
template<typename G>
concept weighted_graph_type = graph_type<G> && graph_traits<G>::is_weighted;
template<typename G>
concept weighted_digraph_type = digraph_type<G> && graph_traits<G>::is_weighted;
template<typename G>
concept weighted_undirected_graph_type = undirected_graph_type<G> && graph_traits<G>::is_weighted;
}
#line 1 "cp-algo/structures/stack_union.hpp"
#line 1 "cp-algo/util/big_alloc.hpp"
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <cstddef>
#include <bit>
#line 14 "cp-algo/util/big_alloc.hpp"
#include <forward_list>
// Single macro to detect POSIX platforms (Linux, Unix, macOS)
#if defined(__linux__) || defined(__unix__) || (defined(__APPLE__) && defined(__MACH__))
#define CP_ALGO_USE_MMAP 1
#include <sys/mman.h>
#else
#define CP_ALGO_USE_MMAP 0
#endif
namespace cp_algo {
template<typename T, size_t Align = 32>
class big_alloc {
static_assert(Align >= alignof(void*), "Align must be at least pointer-size");
static_assert(std::has_single_bit(Align), "Align must be a power of two");
public:
using value_type = T;
template<class U>
struct rebind {
using other = big_alloc<U, Align>;
};
constexpr bool operator==(const big_alloc&) const = default;
big_alloc() noexcept = default;
template<typename U, std::size_t A>
big_alloc(const big_alloc<U, A>&) noexcept {}
[[nodiscard]] T* allocate(std::size_t n) {
std::size_t padded = round_up(n * sizeof(T));
std::size_t align = std::max<std::size_t>(alignof(T), Align);
#if CP_ALGO_USE_MMAP
if(padded >= MEGABYTE) {
void* raw = mmap(nullptr, padded, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
madvise(raw, padded, MADV_HUGEPAGE);
return static_cast<T*>(raw);
}
#endif
return static_cast<T*>(::operator new(padded, std::align_val_t(align)));
}
void deallocate(T* p, std::size_t n) noexcept {
if(!p) {
return;
}
std::size_t padded = round_up(n * sizeof(T));
std::size_t align = std::max<std::size_t>(alignof(T), Align);
#if CP_ALGO_USE_MMAP
if(padded >= MEGABYTE) {
munmap(p, padded);
return;
}
#endif
::operator delete(p, padded, std::align_val_t(align));
}
private:
static constexpr std::size_t MEGABYTE = 1 << 20;
static constexpr std::size_t round_up(std::size_t x) noexcept {
return (x + Align - 1) / Align * Align;
}
};
template<typename T>
using big_vector = std::vector<T, big_alloc<T>>;
template<typename T>
using big_basic_string = std::basic_string<T, std::char_traits<T>, big_alloc<T>>;
template<typename T>
using big_deque = std::deque<T, big_alloc<T>>;
template<typename T>
using big_stack = std::stack<T, big_deque<T>>;
template<typename T>
using big_queue = std::queue<T, big_deque<T>>;
template<typename T>
using big_priority_queue = std::priority_queue<T, big_vector<T>>;
template<typename T>
using big_forward_list = std::forward_list<T, big_alloc<T>>;
using big_string = big_basic_string<char>;
template<typename Key, typename Value, typename Compare = std::less<Key>>
using big_map = std::map<Key, Value, Compare, big_alloc<std::pair<const Key, Value>>>;
template<typename T, typename Compare = std::less<T>>
using big_multiset = std::multiset<T, Compare, big_alloc<T>>;
template<typename T, typename Compare = std::less<T>>
using big_set = std::set<T, Compare, big_alloc<T>>;
}
#line 5 "cp-algo/structures/stack_union.hpp"
#include <iterator>
#include <ranges>
namespace cp_algo::structures {
template<class datatype>
struct stack_union {
stack_union(int n = 0): head(n), next(1), data(1) {}
void push(int v, datatype const& vdata) {
next.push_back(head[v]);
head[v] = (int)std::size(next) - 1;
data.push_back(vdata);
}
template<typename... Args>
void emplace(int v, Args&&... vdata) {
next.push_back(head[v]);
head[v] = (int)std::size(next) - 1;
data.emplace_back(std::forward<Args>(vdata)...);
}
void reserve(int m) {
data.reserve(m);
next.reserve(m);
}
size_t size() const {return std::size(head);}
size_t nodes() const {return std::size(data);}
template<typename Su>
struct _iterator {
using value_type = std::conditional_t<std::is_const_v<Su>, const datatype, datatype>;
using difference_type = std::ptrdiff_t;
Su* su = nullptr;
int sv = 0;
value_type& operator*() const { return su->data[sv]; }
_iterator& operator++() {
sv = su->next[sv];
return *this;
}
_iterator operator++(int) { auto tmp = *this; ++*this; return tmp; }
friend bool operator==(_iterator const& it, std::default_sentinel_t) {
return it.sv == 0;
}
};
using iterator = _iterator<stack_union<datatype>>;
using const_iterator = _iterator<const stack_union<datatype>>;
auto operator[](this auto&& self, int v) {
using Iter = _iterator<std::remove_reference_t<decltype(self)>>;
return std::ranges::subrange(Iter{&self, self.head[v]}, std::default_sentinel);
}
big_vector<int> head, next;
big_vector<datatype> data;
};
}
#line 7 "cp-algo/graph/base.hpp"
namespace cp_algo::graph {
using edge_index = int;
template<edge_type _edge_t = edge_base, graph_mode _mode = undirected>
struct graph {
using edge_t = _edge_t;
static constexpr auto mode = _mode;
using incidence_list = structures::stack_union<edge_index>;
graph(int n, int v0 = 0): v0(v0), adj(n) {}
graph transpose() const {
static_assert(mode == directed, "transpose is only defined for directed graphs");
graph<edge_t, mode> gt(n(), v0);
for(auto v: nodes()) {
for(auto e: outgoing(v)) {
gt.add_edge(edge(e).traverse(v), edge(e));
}
}
return gt;
}
edge_index add_edge(node_index u, edge_t e) {
edge_index idx = (edge_index)size(E);
E.push_back(e);
adj.push(u, idx);
if constexpr (mode == undirected) {
adj.push(e.traverse(u), idx);
}
return idx;
}
edge_index add_edge(node_index u, auto... Args) {
return add_edge(u, edge_t(u, Args...));
}
void read_edges(node_index m) {
adj.reserve(mode == undirected ? 2 * m : m);
for(edge_index i = 0; i < m; i++) {
auto [u, e] = edge_t::read(v0);
add_edge(u, e);
}
}
auto outgoing(node_index v) const {return adj[v];}
auto edges() const {return E | std::views::all;}
auto nodes() const {return std::views::iota(node_index(0), n());}
auto edge_indices() const {return std::views::iota(edge_index(0), m());}
auto&& incidence_lists(this auto&& self) {return self.adj;}
auto&& edge(this auto&& self, edge_index e) {return self.E[e];}
node_index n() const {return (node_index)incidence_lists().size();}
edge_index m() const {return (edge_index)edges().size();}
private:
node_index v0;
big_vector<edge_t> E;
incidence_list adj;
};
// aliases for most standard cases
template<edge_type edge_t = edge_base>
using digraph = graph<edge_t, directed>;
template<weighted_edge_type edge_t = weighted_edge, graph_mode mode = undirected>
using weighted_graph = graph<edge_t, mode>;
template<weighted_edge_type edge_t = weighted_edge>
using weighted_digraph = digraph<edge_t>;
}
#line 4 "cp-algo/graph/dfs.hpp"
#include <variant>
#line 6 "cp-algo/graph/dfs.hpp"
namespace cp_algo::graph {
enum node_state { unvisited, visiting, visited, blocked };
template<graph_type graph>
struct dfs_context {
big_vector<node_state> state;
graph const* g;
bool done = false; // Set to true to stop DFS early
dfs_context(graph const& g): state(g.n()), g(&g) {}
// Called when first entering a node
void on_enter(node_index) {}
// Called when discovering a tree edge (v->u is a tree edge, u is unvisited)
void on_tree_edge(node_index, edge_index) {}
// Called after returning from a child via tree edge
void on_return_from_child(node_index, edge_index) {}
// Called when encountering a back edge (v->u, u is visiting)
void on_back_edge(node_index, edge_index) {}
// Called when encountering a forward/cross edge (v->u, u is visited)
void on_forward_cross_edge(node_index, edge_index) {}
// Called when exiting a node (all edges processed)
void on_exit(node_index) {}
};
template<template<typename> class Context, graph_type graph>
Context<graph> dfs(graph const& g) {
Context<graph> context(g);
auto const& adj = g.incidence_lists();
struct frame {
node_index v;
[[no_unique_address]] std::conditional_t<
undirected_graph_type<graph>,
edge_index, std::monostate> ep;
int sv; // edge index in stack_union
enum { INIT, PROCESS_EDGES, HANDLE_CHILD } state;
};
big_stack<frame> dfs_stack;
for (auto root: g.nodes()) {
if (context.done) break;
if (context.state[root] != unvisited) continue;
if constexpr (undirected_graph_type<graph>) {
dfs_stack.push({root, -1, 0, frame::INIT});
} else {
dfs_stack.push({root, {}, 0, frame::INIT});
}
while (!empty(dfs_stack)) {
auto& f = dfs_stack.top();
if (f.state == frame::INIT) {
context.state[f.v] = visiting;
context.on_enter(f.v);
f.sv = adj.head[f.v];
f.state = frame::PROCESS_EDGES;
continue;
}
if (f.state == frame::HANDLE_CHILD) {
auto e = adj.data[f.sv];
f.sv = adj.next[f.sv];
context.on_return_from_child(f.v, e);
f.state = frame::PROCESS_EDGES;
continue;
}
// PROCESS_EDGES
bool found_child = false;
while (f.sv != 0 && !context.done) {
auto e = adj.data[f.sv];
if constexpr (undirected_graph_type<graph>) {
if (f.ep == e) {
f.sv = adj.next[f.sv];
continue;
}
}
node_index u = g.edge(e).traverse(f.v);
if (context.state[u] == unvisited) {
context.on_tree_edge(f.v, e);
f.state = frame::HANDLE_CHILD;
if constexpr (undirected_graph_type<graph>) {
dfs_stack.push({u, e, 0, frame::INIT});
} else {
dfs_stack.push({u, {}, 0, frame::INIT});
}
found_child = true;
break;
} else if (context.state[u] == visiting) {
context.on_back_edge(f.v, e);
} else if (context.state[u] == visited) {
context.on_forward_cross_edge(f.v, e);
}
f.sv = adj.next[f.sv];
}
if (found_child) continue;
// All edges processed
context.state[f.v] = visited;
context.on_exit(f.v);
dfs_stack.pop();
}
}
return context;
}
}
#line 5 "cp-algo/graph/dfs_time.hpp"
namespace cp_algo::graph {
// Context that maintains discovery time (tin)
template<graph_type graph>
struct dfs_time_context: dfs_context<graph> {
using base = dfs_context<graph>;
big_vector<int> tin;
int timer;
dfs_time_context(graph const& g): base(g), tin(g.n()), timer(0) {}
void on_enter(node_index v) {
tin[v] = timer++;
}
};
// Context that maintains both discovery time (tin) and finish time (tout)
template<graph_type graph>
struct dfs_time_range_context: dfs_time_context<graph> {
using base = dfs_time_context<graph>;
big_vector<int> tout;
dfs_time_range_context(graph const& g): base(g), tout(g.n()) {}
void on_exit(node_index v) {
tout[v] = base::timer;
}
};
// Context that maintains tin and low (for Tarjan-like algorithms)
template<graph_type graph>
struct dfs_low_context: dfs_time_context<graph> {
using base = dfs_time_context<graph>;
big_vector<int> low;
dfs_low_context(graph const& g): base(g), low(g.n()) {}
void on_enter(node_index v) {
base::on_enter(v);
low[v] = base::tin[v];
}
void on_return_from_child(node_index v, edge_index e) {
node_index u = base::g->edge(e).traverse(v);
low[v] = std::min(low[v], low[u]);
}
void on_back_edge(node_index v, edge_index e) {
node_index u = base::g->edge(e).traverse(v);
low[v] = std::min(low[v], base::tin[u]);
}
void on_forward_cross_edge(node_index v, edge_index e) {
node_index u = base::g->edge(e).traverse(v);
low[v] = std::min(low[v], base::tin[u]);
}
};
}
#line 1 "cp-algo/structures/csr.hpp"
#line 4 "cp-algo/structures/csr.hpp"
#include <algorithm>
#include <numeric>
#line 7 "cp-algo/structures/csr.hpp"
#include <span>
namespace cp_algo::structures {
template<class datatype>
struct csr {
csr(): head{0} { }
void new_row() {
head.push_back(head.back());
}
void push(datatype const& value) {
data.push_back(value);
head.back()++;
}
template<typename... Args>
void emplace(Args&&... args) {
data.emplace_back(std::forward<Args>(args)...);
head.back()++;
}
void reserve_rows(int n) {
head.reserve(n + 1);
}
void reserve_data(size_t n) {
data.reserve(n);
}
void reverse_rows() {
std::ranges::reverse(data);
std::adjacent_difference(head.begin(), head.end(), head.begin());
std::ranges::reverse(head | std::views::drop(1));
std::partial_sum(head.begin(), head.end(), head.begin());
}
size_t size() const { return head.size() - 1; }
size_t total_size() const { return data.size(); }
auto operator[](this auto&& self, auto row) {
return std::span(self.data).subspan(self.head[row], self.head[row + 1] - self.head[row]);
}
auto rows(this auto&& self) {
return std::views::iota(size_t(0), self.size())
| std::views::transform([&self](auto i) { return self[i]; });
}
big_vector<int> head;
big_vector<datatype> data;
};
}
#line 7 "cp-algo/graph/tarjan.hpp"
#include <cassert>
#line 9 "cp-algo/graph/tarjan.hpp"
namespace cp_algo::graph {
// Add stack and components collection
template<graph_type graph>
struct tarjan_context: dfs_low_context<graph> {
using base = dfs_low_context<graph>;
big_stack<int> stack;
structures::csr<node_index> components;
tarjan_context(graph const& g): base(g) {
components.reserve_data(g.n());
}
void on_enter(node_index v) {
base::on_enter(v);
stack.push(v);
}
void collect(node_index v) {
components.new_row();
node_index u;
do {
u = stack.top();
stack.pop();
base::state[u] = blocked;
components.push(u);
} while(u != v);
}
};
template<graph_type graph>
struct exit_context: tarjan_context<graph> {
using tarjan_context<graph>::tarjan_context;
void on_exit(node_index v) {
if (this->low[v] == this->tin[v]) {
this->collect(v);
}
}
};
// Tarjan's algorithm for Strongly Connected Components
// returns components in reverse topological order
template<digraph_type graph>
auto strongly_connected_components(graph const& g) {
return dfs<exit_context>(g).components;
}
// Tarjan's algorithm for Two-Edge-Connected Components
template<undirected_graph_type graph>
auto two_edge_connected_components(graph const& g) {
return dfs<exit_context>(g).components;
}
template<undirected_graph_type graph>
struct bcc_context: tarjan_context<graph> {
using base = tarjan_context<graph>;
using base::base;
void on_return_from_child(node_index v, edge_index e) {
base::on_return_from_child(v, e);
node_index u = base::g->edge(e).traverse(v);
if (base::low[u] >= base::tin[v]) {
base::collect(u);
base::components.push(v);
}
}
void on_exit(node_index v) {
if (std::empty(base::g->outgoing(v))) {
base::collect(v);
}
}
};
// Tarjan's algorithm for Biconnected Components (vertex-biconnected)
template<undirected_graph_type graph>
auto biconnected_components(graph const& g) {
return dfs<bcc_context>(g).components;
}
}
#line 8 "verify/graph/2cc.test.cpp"
#include <bits/stdc++.h>
using namespace std;
using namespace cp_algo::graph;
void solve() {
int n, m;
cin >> n >> m;
graph g(n);
g.read_edges(m);
auto comps = two_edge_connected_components(g);
cout << size(comps) << '\n';
for(auto const& comp: comps.rows()) {
cout << size(comp) << ' ';
for(auto v: comp) {
cout << v << ' ';
}
cout << '\n';
}
}
signed main() {
//freopen("input.txt", "r", stdin);
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
//cin >> t;
while(t--) {
solve();
}
}
| Env | Name | Status | Elapsed | Memory |
|---|---|---|---|---|
| g++ | example_00 |
|
3 ms | 4 MB |
| g++ | example_01 |
|
2 ms | 4 MB |
| g++ | example_02 |
|
2 ms | 4 MB |
| g++ | large_cycle_00 |
|
30 ms | 12 MB |
| g++ | max_random_00 |
|
76 ms | 14 MB |
| g++ | max_random_01 |
|
70 ms | 14 MB |
| g++ | max_random_02 |
|
71 ms | 14 MB |
| g++ | random_1_00 |
|
50 ms | 10 MB |
| g++ | random_1_01 |
|
51 ms | 12 MB |
| g++ | random_1_02 |
|
31 ms | 8 MB |
| g++ | random_2_00 |
|
17 ms | 6 MB |
| g++ | random_2_01 |
|
5 ms | 4 MB |
| g++ | random_2_02 |
|
25 ms | 7 MB |
| g++ | random_2_03 |
|
33 ms | 8 MB |
| g++ | random_2_04 |
|
14 ms | 5 MB |
| g++ | small_random_1_00 |
|
2 ms | 4 MB |
| g++ | small_random_1_01 |
|
2 ms | 4 MB |
| g++ | small_random_1_02 |
|
2 ms | 4 MB |
| g++ | small_random_2_00 |
|
2 ms | 4 MB |
| g++ | small_random_2_01 |
|
2 ms | 4 MB |
| g++ | small_random_2_02 |
|
2 ms | 4 MB |