This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <set>
#include <vector>
#include "atcoder/scc"
#include "graph/lowlink.hpp"
#include "graph/quotient_graph.hpp"
int main() {
std::mt19937 rng(20261029);
for (int trial = 0; trial < 2000; trial++) {
int n = 1 + rng() % 8;
int m = rng() % 16;
atcoder::scc_graph sg(n);
std::vector<std::vector<int>> g(n);
std::vector<std::vector<bool>> reach(n, std::vector<bool>(n, false));
for (int i = 0; i < n; i++) reach[i][i] = true;
for (int i = 0; i < m; i++) {
int u = rng() % n, v = rng() % n;
sg.add_edge(u, v);
g[u].push_back(v);
reach[u][v] = true;
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);
}
}
std::vector<std::vector<int>> scc = sg.scc();
std::vector<int> id = component_id(n, scc);
std::vector<std::vector<int>> dag = quotient_graph(g, scc);
int k = int(scc.size());
assert(int(dag.size()) == k);
for (int u = 0; u < n; u++) {
assert(0 <= id[u] && id[u] < k);
for (int v = 0; v < n; v++) assert((id[u] == id[v]) == (reach[u][v] && reach[v][u]));
for (int v : g[u]) assert(id[u] <= id[v]);
}
for (int i = 0; i < k; i++) {
for (int v : scc[i]) assert(id[v] == i);
}
std::vector<std::set<int>> expect(k);
for (int u = 0; u < n; u++) {
for (int v : g[u]) {
if (id[u] != id[v]) expect[id[u]].insert(id[v]);
}
}
for (int i = 0; i < k; i++) {
assert(dag[i] == std::vector<int>(expect[i].begin(), expect[i].end()));
for (int j : dag[i]) assert(i < j);
}
}
for (int trial = 0; trial < 2000; trial++) {
int n = 1 + rng() % 8;
int m = rng() % 12;
lowlink lk(n);
std::vector<std::vector<int>> g(n);
for (int i = 0; i < m; i++) {
int u = rng() % n, v = rng() % n;
lk.add_edge(u, v);
g[u].push_back(v);
g[v].push_back(u);
}
lk.build();
std::vector<std::vector<int>> comps = lk.two_edge_connected_components();
std::vector<int> id = component_id(n, comps);
std::vector<std::vector<int>> tree = quotient_graph(g, comps);
int k = int(comps.size());
int edges = 0;
for (int i = 0; i < k; i++) {
edges += int(tree[i].size());
for (int j : tree[i]) assert(std::ranges::binary_search(tree[j], i));
}
assert(edges == 2 * int(lk.bridges().size()));
for (int v = 0; v < n; v++) assert(id[v] == lk.component(v));
}
std::cout << "Hello World\n";
}#line 1 "test/unit/quotient_graph.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <set>
#include <vector>
#line 1 "atcoder/scc.hpp"
#line 7 "atcoder/scc.hpp"
#line 1 "atcoder/internal_scc.hpp"
#line 5 "atcoder/internal_scc.hpp"
#include <utility>
#line 7 "atcoder/internal_scc.hpp"
#line 1 "atcoder/internal_csr.hpp"
#line 7 "atcoder/internal_csr.hpp"
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
#line 9 "atcoder/internal_scc.hpp"
namespace atcoder {
namespace internal {
// Reference:
// R. Tarjan,
// Depth-First Search and Linear Graph Algorithms
struct scc_graph {
public:
explicit scc_graph(int n) : _n(n) {}
int num_vertices() { return _n; }
void add_edge(int from, int to) { edges.push_back({from, {to}}); }
// @return pair of (# of scc, scc id)
std::pair<int, std::vector<int>> scc_ids() {
auto g = csr<edge>(_n, edges);
int now_ord = 0, group_num = 0;
std::vector<int> visited, low(_n), ord(_n, -1), ids(_n);
visited.reserve(_n);
auto dfs = [&](auto self, int v) -> void {
low[v] = ord[v] = now_ord++;
visited.push_back(v);
for (int i = g.start[v]; i < g.start[v + 1]; i++) {
auto to = g.elist[i].to;
if (ord[to] == -1) {
self(self, to);
low[v] = std::min(low[v], low[to]);
} else {
low[v] = std::min(low[v], ord[to]);
}
}
if (low[v] == ord[v]) {
while (true) {
int u = visited.back();
visited.pop_back();
ord[u] = _n;
ids[u] = group_num;
if (u == v) break;
}
group_num++;
}
};
for (int i = 0; i < _n; i++) {
if (ord[i] == -1) dfs(dfs, i);
}
for (auto& x : ids) {
x = group_num - 1 - x;
}
return {group_num, ids};
}
std::vector<std::vector<int>> scc() {
auto ids = scc_ids();
int group_num = ids.first;
std::vector<int> counts(group_num);
for (auto x : ids.second) counts[x]++;
std::vector<std::vector<int>> groups(ids.first);
for (int i = 0; i < group_num; i++) {
groups[i].reserve(counts[i]);
}
for (int i = 0; i < _n; i++) {
groups[ids.second[i]].push_back(i);
}
return groups;
}
private:
int _n;
struct edge {
int to;
};
std::vector<std::pair<int, edge>> edges;
};
} // namespace internal
} // namespace atcoder
#line 9 "atcoder/scc.hpp"
namespace atcoder {
struct scc_graph {
public:
scc_graph() : internal(0) {}
explicit scc_graph(int n) : internal(n) {}
void add_edge(int from, int to) {
int n = internal.num_vertices();
assert(0 <= from && from < n);
assert(0 <= to && to < n);
internal.add_edge(from, to);
}
std::vector<std::vector<int>> scc() { return internal.scc(); }
private:
internal::scc_graph internal;
};
} // namespace atcoder
#line 6 "graph/lowlink.hpp"
struct lowlink {
public:
lowlink() : lowlink(0) {
}
explicit lowlink(int n) : _n(n), g(n), ord(n, -1), low(n), comp(n, -1), art(n, false) {
}
int add_edge(int u, int v) {
assert(0 <= u && u < _n);
assert(0 <= v && v < _n);
int e = int(edges.size());
edges.emplace_back(u, v);
g[u].emplace_back(v, e);
g[v].emplace_back(u, e);
return e;
}
void build() {
int m = int(edges.size());
bridge.assign(m, false);
std::vector<int> it(_n, 0), par_edge(_n, -1), children(_n, 0);
int t = 0;
for (int r = 0; r < _n; r++) {
if (ord[r] != -1) continue;
std::vector<int> st = {r};
ord[r] = low[r] = t++;
while (!st.empty()) {
int v = st.back();
if (it[v] < int(g[v].size())) {
auto [u, e] = g[v][it[v]++];
if (e == par_edge[v]) continue;
if (ord[u] == -1) {
ord[u] = low[u] = t++;
par_edge[u] = e;
children[v]++;
st.push_back(u);
} else {
low[v] = std::min(low[v], ord[u]);
}
} else {
st.pop_back();
if (st.empty()) continue;
int p = st.back();
low[p] = std::min(low[p], low[v]);
if (low[v] > ord[p]) bridge[par_edge[v]] = true;
if (low[v] >= ord[p] && p != r) art[p] = true;
}
}
art[r] = children[r] >= 2;
}
_num_components = 0;
for (int r = 0; r < _n; r++) {
if (comp[r] != -1) continue;
comp[r] = _num_components;
std::vector<int> st = {r};
while (!st.empty()) {
int v = st.back();
st.pop_back();
for (auto [u, e] : g[v]) {
if (bridge[e] || comp[u] != -1) continue;
comp[u] = _num_components;
st.push_back(u);
}
}
_num_components++;
}
}
bool is_bridge(int e) const {
assert(0 <= e && e < int(edges.size()));
return bridge[e];
}
bool is_articulation(int v) const {
assert(0 <= v && v < _n);
return art[v];
}
std::vector<int> bridges() const {
std::vector<int> res;
for (int e = 0; e < int(edges.size()); e++) {
if (bridge[e]) res.push_back(e);
}
return res;
}
std::vector<int> articulation_points() const {
std::vector<int> res;
for (int v = 0; v < _n; v++) {
if (art[v]) res.push_back(v);
}
return res;
}
int component(int v) const {
assert(0 <= v && v < _n);
return comp[v];
}
std::vector<std::vector<int>> two_edge_connected_components() const {
std::vector<std::vector<int>> res(_num_components);
for (int v = 0; v < _n; v++) res[comp[v]].push_back(v);
return res;
}
private:
int _n, _num_components = 0;
std::vector<std::vector<std::pair<int, int>>> g;
std::vector<std::pair<int, int>> edges;
std::vector<int> ord, low, comp;
std::vector<bool> art, bridge;
};
#line 4 "graph/quotient_graph.hpp"
inline std::vector<int> component_id(int n, const std::vector<std::vector<int>>& groups) {
std::vector<int> id(n);
for (int i = 0; i < int(groups.size()); i++) {
for (int v : groups[i]) id[v] = i;
}
return id;
}
inline std::vector<std::vector<int>> quotient_graph(const std::vector<std::vector<int>>& g, const std::vector<std::vector<int>>& groups) {
std::vector<int> id = component_id(int(g.size()), groups);
std::vector<std::vector<int>> q(groups.size());
for (int u = 0; u < int(g.size()); u++) {
for (int v : g[u]) {
if (id[u] != id[v]) q[id[u]].push_back(id[v]);
}
}
for (auto& es : q) {
std::ranges::sort(es);
es.erase(std::ranges::unique(es).begin(), es.end());
}
return q;
}
#line 12 "test/unit/quotient_graph.test.cpp"
int main() {
std::mt19937 rng(20261029);
for (int trial = 0; trial < 2000; trial++) {
int n = 1 + rng() % 8;
int m = rng() % 16;
atcoder::scc_graph sg(n);
std::vector<std::vector<int>> g(n);
std::vector<std::vector<bool>> reach(n, std::vector<bool>(n, false));
for (int i = 0; i < n; i++) reach[i][i] = true;
for (int i = 0; i < m; i++) {
int u = rng() % n, v = rng() % n;
sg.add_edge(u, v);
g[u].push_back(v);
reach[u][v] = true;
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);
}
}
std::vector<std::vector<int>> scc = sg.scc();
std::vector<int> id = component_id(n, scc);
std::vector<std::vector<int>> dag = quotient_graph(g, scc);
int k = int(scc.size());
assert(int(dag.size()) == k);
for (int u = 0; u < n; u++) {
assert(0 <= id[u] && id[u] < k);
for (int v = 0; v < n; v++) assert((id[u] == id[v]) == (reach[u][v] && reach[v][u]));
for (int v : g[u]) assert(id[u] <= id[v]);
}
for (int i = 0; i < k; i++) {
for (int v : scc[i]) assert(id[v] == i);
}
std::vector<std::set<int>> expect(k);
for (int u = 0; u < n; u++) {
for (int v : g[u]) {
if (id[u] != id[v]) expect[id[u]].insert(id[v]);
}
}
for (int i = 0; i < k; i++) {
assert(dag[i] == std::vector<int>(expect[i].begin(), expect[i].end()));
for (int j : dag[i]) assert(i < j);
}
}
for (int trial = 0; trial < 2000; trial++) {
int n = 1 + rng() % 8;
int m = rng() % 12;
lowlink lk(n);
std::vector<std::vector<int>> g(n);
for (int i = 0; i < m; i++) {
int u = rng() % n, v = rng() % n;
lk.add_edge(u, v);
g[u].push_back(v);
g[v].push_back(u);
}
lk.build();
std::vector<std::vector<int>> comps = lk.two_edge_connected_components();
std::vector<int> id = component_id(n, comps);
std::vector<std::vector<int>> tree = quotient_graph(g, comps);
int k = int(comps.size());
int edges = 0;
for (int i = 0; i < k; i++) {
edges += int(tree[i].size());
for (int j : tree[i]) assert(std::ranges::binary_search(tree[j], i));
}
assert(edges == 2 * int(lk.bridges().size()));
for (int v = 0; v < n; v++) assert(id[v] == lk.component(v));
}
std::cout << "Hello World\n";
}