AtCoder Regular Contest 039 D - 旅行会社高橋君
これは知らなかったので仕方ない…
解法
解説(AtCoder Regular Contest 039 解説)の通り。
実装について簡単に説明しておきます。
最初の方に書いてあるvisitとかbridgeとかはこのページ(Spaghetti Source - 橋,二重辺連結成分分解)を参考というかコピペしました。
この関数で解説にあるような二重辺連結成分分解をやっています。最初グラフの橋についてはこのページ(橋と関節点, lowlink - Lilliput Steps)を参考にしていたので「このvisitとか何やってるんや!」と思いましたが,これは別の方法(AtCoderの解説に書いてあるようなやり方)で橋や二重辺連結成分を求めているようです。
このvisitの関数内の
else if (u != w && inS[w]) while (num[roots.top()] > num[w]) roots.pop();
この部分がAtCoderの解説で言うところの「後退辺ごとに、対応するパス上の辺を塗る」という部分に対応しているんだと思います(rootsのスタックをpopしていくことで関係ない辺は外していっている)。
その後は二重辺連結成分それぞれをひとつのノードとみなして木を構成し,ゴニョゴニョしますが,そこは以前に作ったクラスTreeが担当しています。これも解説の通りやっているだけですね。
以下ソースコード
struct Edge { int src, dst; Edge(int src, int dst) : src(src), dst(dst) {} }; typedef vector<Edge> Edges; typedef vector<Edges> Graph; void visit(const Graph & g, int v, int u, Edges& brdg, vector< vector<int> >& tecomp, stack<int>& roots, stack<int>& S, vector<bool>& inS, vector<int>& num, int& time) { num[v] = ++time; S.push(v); inS[v] = true; roots.push(v); for (auto e : g[v]) { int w = e.dst; if (num[w] == 0) visit(g, w, v, brdg, tecomp, roots, S, inS, num, time); else if (u != w && inS[w]) while (num[roots.top()] > num[w]) roots.pop(); } if (v == roots.top()) { brdg.push_back(Edge(u, v)); tecomp.push_back(vector<int>()); while (1) { int w = S.top(); S.pop(); inS[w] = false; tecomp.back().push_back(w); if (v == w) break; } roots.pop(); } } void bridge(const Graph& g, Edges& brdg, vector< vector<int> >& tecomp) { const int n = g.size(); vector<int> num(n); vector<bool> inS(n); stack<int> roots, S; int time = 0; for (int u = 0; u < n; u++) if (num[u] == 0) { visit(g, u, n, brdg, tecomp, roots, S, inS, num, time); brdg.pop_back(); } } // Tree->unite->init class Tree { public: Tree(int V, int root) : V(V), root(root) { T.resize(V); for (int i = 0; i < MAXLOGV; i++) parent[i].resize(V); depth.resize(V); } // uとvをつなぐ // lcaを求めることが主目的なので無向グラフとしている void unite(int u, int v) { T[u].push_back(v); T[v].push_back(u); } // initする // コンストラクタだけじゃなくてこれも呼ばないとlcaが求められないぞ void init() { dfs(root, -1, 0); for (int k = 0; k+1 < MAXLOGV; k++) { for (int v = 0; v < V; v++) { if (parent[k][v] < 0) parent[k+1][v] = -1; else parent[k+1][v] = parent[k][parent[k][v]]; } } } // uとvのlcaを求める int lca(int u, int v) const { if (depth[u] > depth[v]) swap(u, v); for (int k = 0; k < MAXLOGV; k++) { if ((depth[v] - depth[u])>>k & 1) { v = parent[k][v]; } } if (u == v) return u; for (int k = MAXLOGV-1; k >= 0; k--) { if (parent[k][u] != parent[k][v]) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } // uとvの距離を求める // edgeを定義しないといけない時はこれじゃダメ int dist(int u, int v) const { int p = lca(u, v); return (depth[u]-depth[p]) + (depth[v]-depth[p]); } void dfs(int v, int p, int d) { parent[0][v] = p; depth[v] = d; for (int next : T[v]) { if (next != p) dfs(next, v, d+1); } } static const int MAXLOGV = 25; // グラフの隣接リスト表現 vector<vector<int> > T; // 頂点の数 int V; // 根ノードの番号 int root; // 親ノード vector<int> parent[MAXLOGV]; // 根からの深さ vector<int> depth; }; const int MAXN = 100100; int A[MAXN]; int main() { cin.tie(0); ios::sync_with_stdio(false); int N, M; cin >> N >> M; Graph g; g.resize(N); for (int i = 0; i < M; i++) { int x, y; cin >> x >> y; x--; y--; g[x].push_back(Edge(x, y)); g[y].push_back(Edge(y, x)); } Edges brdg; vector<vi> tecomp; bridge(g, brdg, tecomp); int n = tecomp.size(); for (int i = 0; i < n; i++) { for (int el : tecomp[i]) { A[el] = i; } } Tree* tree = new Tree(n+1, 0); for (int i = 0; i < (int)brdg.size(); i++) { int u = A[brdg[i].src], v = A[brdg[i].dst]; tree->unite(u, v); } tree->init(); int Q; cin >> Q; while (Q--) { int a, b, c; cin >> a >> b >> c; a--; b--; c--; if (A[a] == A[b] && A[b] == A[c]) { cout << "OK" << endl; } else { int x = A[a], y = A[b], z = A[c]; if ((tree->dist(x, z)) == (tree->dist(x, y)) + (tree->dist(y, z))) cout << "OK" << endl; else cout << "NG" << endl; } } return 0; }