二重辺連結成分分解ライブラリを整えた。
問題概要
N 頂点, M 辺の無向単純グラフにおいて、以下の Q 個のクエリに答えよ。
- A B C: A から出発して B に行くウォークと、B から出発して C に行くウォークの組のうち、辺を共有しないものがあるかどうかを判定せよ (頂点共有はOK)
制約
- 3 <= N <= 105
- 1 <= M <= 2 × 105
- 1 <= Q <= 105
解法
今の AtCoder では出なさそうなライブラリゲーだけど、こういうのもありがたい。
これは「Aから{B,C}への大きさ2のフローが存在するか?」という問題と思える。
- 大きさ2のフローから「橋」や「二重辺連結成分分解」を連想するのは自然ではある。
- 二重辺連結成分分解してできるツリー上で、パスACの長さ = パスABの長さ + パスBCの長さとなるかどうかを判定すればよい。
全体の計算量は O(N + M + Q logN)
#include <iostream> #include <vector> #include <algorithm> #include <set> using namespace std; #define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P) { return s << '<' << P.first << ", " << P.second << '>'; } template<class T> ostream& operator << (ostream &s, vector<T> P) { for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; } template<class T> ostream& operator << (ostream &s, vector<vector<T> > P) { for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; } using Edge = pair<int,long long>; using Graph = vector<vector<Edge> >; struct BridgeDecomposition { // bridge and articulation points vector<int> aps; // articulation points vector<pair<int,int> > brs; // brideges // decomposition vector<vector<int> > scc; // scc[i] := i'th component vector<int> cmp; // cmp[v] := which component is v belong Graph newG; // the tree // intermediate results vector<int> seen, ord, low; // calc low-link void dfs_lowlink(const Graph &G, int v, int p = -1) { static int time = 0; seen[v] = true; ord[v] = low[v] = time++; int num_of_child = 0; bool exist = false; // for articulation point for (auto ch_edge : G[v]) { int ch = ch_edge.first; if (seen[ch]) { if (ch != p) low[v] = min(low[v], ord[ch]); // back edge continue; } dfs_lowlink(G, ch, v); low[v] = min(low[v], low[ch]); // forward edge of DFS-tree if (ord[v] < low[ch]) brs.emplace_back(v, ch); if (ord[v] <= low[ch]) exist = true; ++num_of_child; } if ((p == -1 && num_of_child > 1) || (p != -1 && exist)) aps.emplace_back(v); } // reconstruct tree vector<int> comp; set<pair<int,int> > newEdges; void MakeTreeDFS(const Graph &G, int v, int curcmp) { seen[v] = true; cmp[v] = curcmp; for (auto e : G[v]) { int to = e.first; auto weight = e.second; bool sameComp = true; if (seen[to]) sameComp = false; if (binary_search(brs.begin(), brs.end(), make_pair(v, to)) || binary_search(brs.begin(), brs.end(), make_pair(to, v))) sameComp = false; if (!sameComp) { int newcmp = cmp[to]; if (newcmp == -1) continue; if (newcmp != curcmp) { if (!newEdges.count(make_pair(curcmp, newcmp)) && !newEdges.count(make_pair(newcmp, curcmp))) { newEdges.insert(make_pair(curcmp, newcmp)); newG[curcmp].push_back(Edge(newcmp, weight)); newG[newcmp].push_back(Edge(curcmp, weight)); } } } else MakeTreeDFS(G, to, curcmp); } comp.push_back(v); } // main void solve(const Graph &G) { // calc low-link int N = (int)G.size(); seen.assign(N, 0); ord.resize(N); low.resize(N); aps.clear(); brs.clear(); for (int v = 0; v < N; ++v) if (!seen[v]) dfs_lowlink(G, v); sort(brs.begin(), brs.end()); // reconstruct tree scc.clear(); newG.clear(); newG.resize(N); newEdges.clear(); seen.assign(N, 0); cmp.assign(N, -1); int tcmp = 0; for (int v = 0; v < N; ++v) { if (seen[v]) continue; comp.clear(); MakeTreeDFS(G, v, tcmp++); scc.push_back(comp); } newG.resize(tcmp); } }; // LCA struct LCA { vector<vector<int> > parent; // parent[d][v] := 2^d-th parent of v vector<int> depth; LCA() { } LCA(const Graph &G, int r = 0) { init(G, r); } void init(const Graph &G, int r = 0) { int V = (int)G.size(); int h = 1; while ((1<<h) < V) ++h; parent.assign(h, vector<int>(V, -1)); depth.assign(V, -1); dfs(G, r, -1, 0); for (int i = 0; i+1 < (int)parent.size(); ++i) for (int v = 0; v < V; ++v) if (parent[i][v] != -1) parent[i+1][v] = parent[i][parent[i][v]]; } void dfs(const Graph &G, int v, int p, int d) { parent[0][v] = p; depth[v] = d; for (auto e : G[v]) if (e.first != p) dfs(G, e.first, v, d+1); } int get(int u, int v) { if (depth[u] > depth[v]) swap(u, v); for (int i = 0; i < (int)parent.size(); ++i) if ( (depth[v] - depth[u]) & (1<<i) ) v = parent[i][v]; if (u == v) return u; for (int i = (int)parent.size()-1; i >= 0; --i) { if (parent[i][u] != parent[i][v]) { u = parent[i][u]; v = parent[i][v]; } } return parent[0][u]; } int dist(int u, int v) { int lca = get(u, v); return abs(depth[u] - depth[lca]) + abs(depth[v] - depth[lca]); } }; int main() { int V, E; cin >> V >> E; Graph G(V); for (int i = 0; i < E; ++i) { int s, t; cin >> s >> t; --s, --t; G[s].push_back(Edge(t, 1)); G[t].push_back(Edge(s, 1)); } BridgeDecomposition bd; bd.solve(G); /* COUT(bd.brs); COUT(bd.newG); COUT(bd.scc); COUT(bd.cmp); */ LCA lca(bd.newG); int Q; cin >> Q; for (int _ = 0; _ < Q; ++_) { int a, b, c; cin >> a >> b >> c; --a, --b, --c; a = bd.cmp[a]; b = bd.cmp[b]; c = bd.cmp[c]; int ab = lca.dist(a, b); int bc = lca.dist(b, c); int ac = lca.dist(a, c); if (ab + bc == ac) puts("OK"); else puts("NG"); } }