This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub crackersamdjam/Codebook
#define PROBLEM "https://judge.yosupo.jp/problem/biconnected_components" #include "../content/graph/tarjan.h" int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin.exceptions(cin.failbit); int n, m; cin >> n >> m; blockcut t(n); for (int i = 0, a, b; i < m; i++) { cin >> a >> b; if (a != b) { t.addedge(a, b); t.addedge(b, a); } } t.run(); cout << size(t.comps) << '\n'; for (auto &&v : t.comps) { cout << size(v); for (auto i : v) cout << ' ' << i; cout << '\n'; } }
#line 1 "tests/tarjan_blockcut_bccs.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/biconnected_components" #line 1 "content/utils/template.h" /** * @brief My starter code */ #include <bits/stdc++.h> #define all(x) (x).begin(), (x).end() #define makeunique(x) (x).erase(unique((x).begin(), (x).end()), (x).end()); #ifdef LOCAL template<typename T> void pr(T a){std::cerr<<a<<std::endl;} template<typename T, typename... Args> void pr(T a, Args... args){std::cerr<<a<<' ',pr(args...);} #else template<typename... Args> void pr(Args... args){} #endif using namespace std; using ll = long long; using pii = pair<int, int>; #line 3 "content/graph/tarjan.h" /** * @brief Tarjan's algorithm * @docs docs/tarjan.md */ struct SCC { int n, t, ii; vector<vector<int>> adj; vector<int> dfn, low, id; vector<bool> ins; stack<int> stk; vector<vector<int>> comps; SCC(int mm) : n(mm), t(0), ii(0), adj(mm), dfn(mm), low(mm), id(mm), ins(mm) {} void addedge(int a, int b) { adj[a].emplace_back(b); } void dfs(int cur) { dfn[cur] = low[cur] = ++t; stk.push(cur); ins[cur] = 1; for (int u: adj[cur]) { if (!dfn[u]) { dfs(u); low[cur] = min(low[cur], low[u]); } else if (ins[u]) low[cur] = min(low[cur], dfn[u]); } if (dfn[cur] == low[cur]) { int u = -1; comps.emplace_back(); while (u != cur) { u = stk.top(); stk.pop(); ins[u] = 0; id[u] = cur; comps.back().emplace_back(u); } } } void run() { for (int i = 0; i < n; i++) { if (!dfn[i]) { dfs(i); } } } }; // Any connected graph decomposes into a tree of **biconnected components (BCCs)** called the **block-cut** tree of the graph struct blockcut { int n, t, ei, ncomps; vector<vector<pii>> adj; vector<vector<int>> adj2, comps; vector<int> dfn, low, id; vector<bool> ins; stack<int> st; set<int> art; blockcut(int mm) : n(mm), t(0), ei(0), ncomps(0), adj(mm), comps(mm), dfn(mm), low(mm), id(mm), ins(mm) {} void addedge(int a, int b) { adj[a].emplace_back(b, ei); adj[b].emplace_back(a, ei); ei++; } void process(int cur){ if (st.empty()) return; while (st.size()) { int u = st.top(); st.pop(); comps[ncomps].push_back(u); if (u == cur) break; } ncomps++; } void dfs(int cur, int pi = -1) { dfn[cur] = low[cur] = ++t; st.push(cur); int ch = 0; for (auto [u, i]: adj[cur]) { if (i == pi) continue; if (!dfn[u]) { ch++; dfs(u, i); low[cur] = min(low[cur], low[u]); if ((pi == -1 and ch > 1) or (pi != -1 and low[u] >= dfn[cur])) { art.insert(cur); st.push(cur); process(u); } } else low[cur] = min(low[cur], dfn[u]); } } // Block leaders are numbered [n, n + ncomps) int run() { for (int i = 0; i < n; i++) { if (!dfn[i]) { dfs(i, -1); st.push(i); process(-1); // pop stack until empty } } comps.resize(ncomps); adj2.resize(n+ncomps); for (int i = 0; i < ncomps; i++) { sort(all(comps[i])); makeunique(comps[i]); for (int u: comps[i]) { adj2[n+i].push_back(u); adj2[u].push_back(n+i); } } return n + ncomps; } }; #line 3 "tests/tarjan_blockcut_bccs.test.cpp" int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin.exceptions(cin.failbit); int n, m; cin >> n >> m; blockcut t(n); for (int i = 0, a, b; i < m; i++) { cin >> a >> b; if (a != b) { t.addedge(a, b); t.addedge(b, a); } } t.run(); cout << size(t.comps) << '\n'; for (auto &&v : t.comps) { cout << size(v); for (auto i : v) cout << ' ' << i; cout << '\n'; } }