sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#define PROBLEM "https://judge.yosupo.jp/problem/biconnected_components" #include "../../graph/biconnected_components.hpp" #include <bits/stdc++.h> #include "../../graph/lowlink.hpp" using namespace std; using ll = long long; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin >> N >> M; vector<vector<int>> G(N); set<pair<int, int>> st; vector<bool> alone(N, true); for (int i = 0; i < M; ++i) { int a, b; cin >> a >> b; if (!st.count(minmax(a, b))) { G[a].push_back(b); G[b].push_back(a); alone[a] = alone[b] = false; } st.insert(minmax(a, b)); } Lowlink low(G); auto comps = biconnected_components(G, low); for (int i = 0; i < N; ++i) { if (alone[i]) { comps.push_back({{i, i}}); } } cout << comps.size() << endl; for (auto& comp : comps) { set<int> st; for (auto [u, v] : comp) { st.insert(u); st.insert(v); } cout << st.size(); for (int i : st) cout << " " << i; cout << "\n"; } }
#line 1 "test/yosupo/biconnected_components.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/biconnected_components" #line 2 "graph/biconnected_components.hpp" #include <stack> #include <utility> #include <vector> #line 2 "graph/lowlink.hpp" #include <algorithm> #line 5 "graph/lowlink.hpp" class Lowlink { public: std::vector<int> ord, low; std::vector<std::pair<int, int>> bridge; std::vector<int> articulation; Lowlink() = default; explicit Lowlink(const std::vector<std::vector<int>>& G) : ord(G.size(), -1), low(G.size()), G(G) { for (int i = 0; i < (int)G.size(); ++i) { if (ord[i] == -1) dfs(i, -1); } } bool is_bridge(int u, int v) const { if (ord[u] > ord[v]) std::swap(u, v); return ord[u] < low[v]; } private: std::vector<std::vector<int>> G; int k = 0; void dfs(int v, int p) { ord[v] = k++; low[v] = ord[v]; bool is_articulation = false, checked = false; int cnt = 0; for (int c : G[v]) { if (c == p && !checked) { checked = true; continue; } if (ord[c] == -1) { ++cnt; dfs(c, v); low[v] = std::min(low[v], low[c]); if (p != -1 && ord[v] <= low[c]) is_articulation = true; if (ord[v] < low[c]) bridge.push_back(std::minmax(v, c)); } else { low[v] = std::min(low[v], ord[c]); } } if (p == -1 && cnt > 1) is_articulation = true; if (is_articulation) articulation.push_back(v); } }; #line 7 "graph/biconnected_components.hpp" std::vector<std::vector<std::pair<int, int>>> biconnected_components( const std::vector<std::vector<int>>& G, const Lowlink& low) { std::vector<bool> used(G.size()); std::stack<std::pair<int, int>> st; std::vector<std::vector<std::pair<int, int>>> bc; auto dfs = [&](auto& dfs, int v, int p) -> void { used[v] = true; for (int c : G[v]) { if (c == p) continue; if (!used[c] || low.ord[c] < low.ord[v]) { st.emplace(v, c); } if (!used[c]) { dfs(dfs, c, v); if (low.ord[v] <= low.low[c]) { // v is an articulation point bc.emplace_back(); while (true) { auto e = st.top(); st.pop(); bc.back().push_back(e); if (e.first == v) { break; } } } } } }; for (int v = 0; v < (int)G.size(); ++v) { if (!used[v]) dfs(dfs, v, -1); } return bc; } #line 4 "test/yosupo/biconnected_components.test.cpp" #include <bits/stdc++.h> #line 8 "test/yosupo/biconnected_components.test.cpp" using namespace std; using ll = long long; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin >> N >> M; vector<vector<int>> G(N); set<pair<int, int>> st; vector<bool> alone(N, true); for (int i = 0; i < M; ++i) { int a, b; cin >> a >> b; if (!st.count(minmax(a, b))) { G[a].push_back(b); G[b].push_back(a); alone[a] = alone[b] = false; } st.insert(minmax(a, b)); } Lowlink low(G); auto comps = biconnected_components(G, low); for (int i = 0; i < N; ++i) { if (alone[i]) { comps.push_back({{i, i}}); } } cout << comps.size() << endl; for (auto& comp : comps) { set<int> st; for (auto [u, v] : comp) { st.insert(u); st.insert(v); } cout << st.size(); for (int i : st) cout << " " << i; cout << "\n"; } }