This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#include "../../../src/template/template.hpp"
#include "../../../src/graph/graph_template.hpp"
#include "../../../src/graph/biconnected_components.hpp"
int main() {
Graph<int> g(2);
g.add_edge(0, 1);
g.add_edge(0, 1);
BiconnectedComponents<int> bc(g);
assert(bc.bc.size() == 1);
assert(bc.bc[0].size() == 2);
Graph<int> h(3);
h.add_edge(0, 1);
h.add_edge(1, 2);
BiconnectedComponents<int> bc2(h);
assert(bc2.bc.size() == 2);
for(const auto& comp : bc2.bc) assert(comp.size() == 1);
int a, b;
cin >> a >> b;
cout << a + b << '\n';
}#line 1 "verify/unit_test/graph/biconnected_components.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
#line 4 "src/template/template.hpp"
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
SetupIO() {
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(30);
}
} setup_io;
#line 3 "src/graph/graph_template.hpp"
template <typename T>
struct Edge {
int from, to;
T cost;
int idx;
Edge()
: from(-1), to(-1), cost(-1), idx(-1) {}
Edge(const int from, const int to, const T& cost = 1, const int idx = -1)
: from(from), to(to), cost(cost), idx(idx) {}
operator int() const {
return to;
}
};
template <typename T>
struct Graph {
Graph(const int N)
: n(N), es(0), g(N) {}
int size() const {
return n;
}
int edge_size() const {
return es;
}
void add_edge(const int from, const int to, const T& cost = 1) {
assert(0 <= from and from < n);
assert(0 <= to and to < n);
g[from].emplace_back(from, to, cost, es);
g[to].emplace_back(to, from, cost, es++);
}
void add_directed_edge(const int from, const int to, const T& cost = 1) {
assert(0 <= from and from < n);
assert(0 <= to and to < n);
g[from].emplace_back(from, to, cost, es++);
}
inline vector<Edge<T>>& operator[](const int& k) {
assert(0 <= k and k < n);
return g[k];
}
inline const vector<Edge<T>>& operator[](const int& k) const {
assert(0 <= k and k < n);
return g[k];
}
private:
int n, es;
vector<vector<Edge<T>>> g;
};
template <typename T>
using Edges = vector<Edge<T>>;
#line 4 "src/graph/low_link.hpp"
template <typename T>
struct LowLink {
vector<int> ord, low, articulation;
vector<pair<int, int>> bridge;
LowLink(const Graph<T>& g)
: ord(g.size(), -1), low(g.size(), -1) {
for(int i = 0, k = 0; i < g.size(); ++i) {
if(ord[i] == -1) k = dfs(g, i, k, -1);
}
}
private:
int dfs(const Graph<T>& g, const int idx, int k, const int par) {
low[idx] = (ord[idx] = k++);
int cnt = 0;
bool arti = false, second = false;
for(const Edge<T>& e : g[idx]) {
const int to = e.to;
if(ord[to] == -1) {
++cnt;
k = dfs(g, to, k, idx);
low[idx] = min(low[idx], low[to]);
arti |= (par != -1) and (low[to] >= ord[idx]);
if(ord[idx] < low[to]) {
bridge.emplace_back(minmax(idx, to));
}
} else if(to != par or second) {
low[idx] = min(low[idx], ord[to]);
} else {
second = true;
}
}
arti |= (par == -1) and (cnt > 1);
if(arti) articulation.emplace_back(idx);
return k;
}
};
#line 5 "src/graph/biconnected_components.hpp"
template <typename T>
struct BiconnectedComponents {
vector<vector<pair<int, int>>> bc;
BiconnectedComponents(const Graph<T>& g)
: n(g.size()), lowlink(g), used(n) {
for(int i = 0; i < n; ++i) {
if(!used[i]) dfs(g, i, -1);
}
}
private:
struct edge_key {
int u, v, idx;
};
int n;
LowLink<T> lowlink;
vector<int> used;
vector<edge_key> tmp;
void dfs(const Graph<T>& g, const int idx, const int par_edge_idx) {
used[idx] = true;
for(const Edge<T>& e : g[idx]) {
const int to = e.to;
if(e.idx == par_edge_idx) continue;
if(!used[to] or lowlink.ord[to] < lowlink.ord[idx]) {
const auto [u, v] = minmax(idx, to);
tmp.push_back({u, v, e.idx});
}
if(!used[to]) {
dfs(g, to, e.idx);
if(lowlink.low[to] >= lowlink.ord[idx]) {
bc.emplace_back();
while(true) {
const edge_key ed = tmp.back();
bc.back().emplace_back(ed.u, ed.v);
tmp.pop_back();
if(ed.idx == e.idx) break;
}
}
}
}
}
};
#line 5 "verify/unit_test/graph/biconnected_components.test.cpp"
int main() {
Graph<int> g(2);
g.add_edge(0, 1);
g.add_edge(0, 1);
BiconnectedComponents<int> bc(g);
assert(bc.bc.size() == 1);
assert(bc.bc[0].size() == 2);
Graph<int> h(3);
h.add_edge(0, 1);
h.add_edge(1, 2);
BiconnectedComponents<int> bc2(h);
assert(bc2.bc.size() == 2);
for(const auto& comp : bc2.bc) assert(comp.size() == 1);
int a, b;
cin >> a >> b;
cout << a + b << '\n';
}