mayoko’s diary

プロコンとかいろいろ。

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;
}