This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub SSRS-cp/cp_library
#define PROBLEM "https://yukicoder.me/problems/no/1326" #include <bits/stdc++.h> using namespace std; #include "../../graph/block_cut_tree.hpp" #include "../../data_structure/tree/heavy_light_decomposition.hpp" int main(){ int N, M; cin >> N >> M; vector<vector<int>> E(N); for (int i = 0; i < M; i++){ int a, b; cin >> a >> b; a--; b--; E[a].push_back(b); E[b].push_back(a); } block_cut_tree G(E); vector<int> id(N, -1); for (int i = 0; i < G.V; i++){ for (int j : G.node[i]){ if (id[j] == -1){ id[j] = i; } } } vector<int> p(G.V, -1); vector<vector<int>> c(G.V); vector<int> d(G.V, 0); if (G.cut[0]){ d[0]++; } queue<int> q; q.push(0); while (!q.empty()){ int v = q.front(); q.pop(); for (int w : G.G[v]){ if (w != p[v]){ p[w] = v; c[v].push_back(w); d[w] = d[v]; if (G.cut[w]){ d[w]++; } q.push(w); } } } heavy_light_decomposition T(p, c); int Q; cin >> Q; for (int i = 0; i < Q; i++){ int x, y; cin >> x >> y; x--; y--; x = id[x]; y = id[y]; if (x == y){ cout << 0 << endl; } else { int z = T.lca(x, y); int ans = d[x] + d[y] - d[z] * 2; if (G.cut[z]){ ans++; } if (G.cut[x]){ ans--; } if (G.cut[y]){ ans--; } cout << ans << endl; } } }
#line 1 "test/yukicoder/yuki_1326.test.cpp" #define PROBLEM "https://yukicoder.me/problems/no/1326" #include <bits/stdc++.h> using namespace std; #line 2 "graph/block_cut_tree.hpp" /** * @brief Block Cut Tree */ #line 2 "graph/biconnected_components.hpp" /** * @brief 二重頂点連結成分分解 */ struct biconnected_components{ vector<int> bcc; int cnt = 0; biconnected_components(vector<vector<pair<int, int>>> &E){ int N = E.size(); vector<int> next(N, -1); vector<int> d(N, -1); vector<int> imos(N, 0); for (int i = 0; i < N; i++){ if (d[i] == -1){ d[i] = 0; dfs1(E, next, d, imos, i); } } int M = 0; for (int i = 0; i < N; i++){ M += E[i].size(); } M /= 2; bcc = vector<int>(M, -1); for (int i = 0; i < N; i++){ if (d[i] == 0){ dfs2(E, d, imos, cnt, i); } } } void dfs1(vector<vector<pair<int, int>>> &E, vector<int> &next, vector<int> &d, vector<int> &imos, int v){ for (auto P : E[v]){ int w = P.second; if (d[w] == -1){ d[w] = d[v] + 1; next[v] = w; dfs1(E, next, d, imos, w); imos[v] += imos[w]; } else if (d[w] < d[v] - 1){ imos[v]++; imos[next[w]]--; } } } void dfs2(vector<vector<pair<int, int>>> &E, vector<int> &d, vector<int> &imos, int b, int v){ for (auto P : E[v]){ int x = P.first; int w = P.second; if (d[w] < d[v]){ bcc[x] = b; } else if (d[w] == d[v] + 1 && bcc[x] == -1){ if (imos[w] > 0){ bcc[x] = b; } else { bcc[x] = cnt; cnt++; } dfs2(E, d, imos, bcc[x], w); } } } int operator [](int k){ return bcc[k]; } }; #line 6 "graph/block_cut_tree.hpp" struct block_cut_tree{ int V; vector<bool> art; vector<bool> cut; vector<vector<int>> G; vector<vector<int>> node; block_cut_tree(vector<vector<int>> &E){ int N = E.size(); int M = 0; vector<vector<pair<int, int>>> E2(N); for (int i = 0; i < N; i++){ for (int j : E[i]){ if (j > i){ E2[i].push_back(make_pair(M, j)); E2[j].push_back(make_pair(M, i)); M++; } } } biconnected_components B(E2); art = vector<bool>(N, false); int cnt = 0; for (int i = 0; i < N; i++){ for (auto P : E2[i]){ if (B[P.first] != B[E2[i][0].first]){ art[i] = true; } } if (art[i]){ cnt++; } if (E[i].empty()){ cnt++; } } V = cnt + B.cnt; cut = vector<bool>(V, false); G.resize(V); node.resize(V); int cnt2 = 0; vector<bool> used(B.cnt, false); for (int i = 0; i < N; i++){ if (art[i]){ cut[cnt2] = true; node[cnt2].push_back(i); for (auto P : E2[i]){ int b = B[P.first]; if (!used[b]){ used[b] = true; G[cnt + b].push_back(cnt2); G[cnt2].push_back(cnt + b); node[cnt + b].push_back(i); } } for (auto P : E2[i]){ int b = B[P.first]; used[b] = false; } cnt2++; } else if (!E2[i].empty()){ int b = B[E2[i][0].first]; node[cnt + b].push_back(i); } else { node[cnt2].push_back(i); cnt2++; } } } }; #line 2 "data_structure/tree/heavy_light_decomposition.hpp" /** * @brief 重軽分解 */ struct heavy_light_decomposition{ vector<int> p, sz, in, next; void dfs1(vector<vector<int>> &c, int v){ sz[v] = 1; for (int &w : c[v]){ dfs1(c, w); sz[v] += sz[w]; if (sz[w] > sz[c[v][0]]){ swap(w, c[v][0]); } } } void dfs2(vector<vector<int>> &c, int &t, int v){ in[v] = t; t++; for (int w : c[v]){ if (w == c[v][0]){ next[w] = next[v]; } else { next[w] = w; } dfs2(c, t, w); } } heavy_light_decomposition(vector<int> &p, vector<vector<int>> &c, int r = 0): p(p){ int N = p.size(); sz = vector<int>(N); dfs1(c, r); in = vector<int>(N); next = vector<int>(N, r); int t = 0; dfs2(c, t, r); } int lca(int u, int v){ while (true){ if (in[u] > in[v]){ swap(u, v); } if (next[u] == next[v]){ return u; } v = p[next[v]]; } } int dist(int u, int v){ int ans = 0; while (true){ if (in[u] > in[v]){ swap(u, v); } if (next[u] == next[v]){ ans += in[v] - in[u]; return ans; } ans += in[v] - in[next[v]] + 1; v = p[next[v]]; } } }; #line 6 "test/yukicoder/yuki_1326.test.cpp" int main(){ int N, M; cin >> N >> M; vector<vector<int>> E(N); for (int i = 0; i < M; i++){ int a, b; cin >> a >> b; a--; b--; E[a].push_back(b); E[b].push_back(a); } block_cut_tree G(E); vector<int> id(N, -1); for (int i = 0; i < G.V; i++){ for (int j : G.node[i]){ if (id[j] == -1){ id[j] = i; } } } vector<int> p(G.V, -1); vector<vector<int>> c(G.V); vector<int> d(G.V, 0); if (G.cut[0]){ d[0]++; } queue<int> q; q.push(0); while (!q.empty()){ int v = q.front(); q.pop(); for (int w : G.G[v]){ if (w != p[v]){ p[w] = v; c[v].push_back(w); d[w] = d[v]; if (G.cut[w]){ d[w]++; } q.push(w); } } } heavy_light_decomposition T(p, c); int Q; cin >> Q; for (int i = 0; i < Q; i++){ int x, y; cin >> x >> y; x--; y--; x = id[x]; y = id[y]; if (x == y){ cout << 0 << endl; } else { int z = T.lca(x, y); int ans = d[x] + d[y] - d[z] * 2; if (G.cut[z]){ ans++; } if (G.cut[x]){ ans--; } if (G.cut[y]){ ans--; } cout << ans << endl; } } }