ARC 039 D 旅行会社高橋君

2015/06/20 (Sat) ARC AtCoder グラフ 木に対するクエリ 橋

問題

日本語

方針

知識として，ある辺について，それを除くとグラフの連結成分が $1$ つ増えるとき，それを橋という． さらに，ある部分グラフについて，そこに橋が含まれないとき，それを二重辺連結成分という． これを求める処理は $O(V+E)$ でできる．

二重辺連結成分に分解し，各成分を $1$ つの頂点に縮約すると木になる． この上で問題を解くのは割と簡単で，クエリ $a, b, c$ が来たとき，$d(a,b) + d(b,c) = d(a,c)$ を満足するか見ればいい．木上の距離クエリは LCA を使えば $O(\log V)$ で処理できる． ただ，簡単と言っても思いつけるかは別の話で，本番中は解けなかった．

実装

int d(int a, int b, int l, vector<Weight> & dist){
    return dist[a] - dist[l] + dist[b] - dist[l];
}
 
signed main(){
 
#ifdef LOCAL
    freopen("in","r",stdin);
#endif
 
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,m;
    cin >> n >> m;
    Graph g(n);
    rep(i,m){
        int x,y;
        cin >> x >> y;
        x--;
        y--;
        g[x].eb(x,y,1);
        g[y].eb(y,x,1);
    }
 
    Edges brdg;
    vector<vector<int>> comp;
    bridge(g,brdg,comp);
    vector<int> dic(n);
    rep(i,comp.size())rep(j,comp[i].size()) dic[comp[i][j]] = i;
 
    LCA lca(comp.size());
    for(auto & e : brdg){
        int a = dic[e.src], b = dic[e.dst];
        lca.add_edge(a,b);
        lca.add_edge(b,a);
    }
    lca.compile(0);
    vector<Weight> dist = dijkstra(lca.g,0);
    int q;
    cin >> q;
    rep(i,q){
        int a,b,c;
        cin >> a >> b >> c;
        a--;
        b--;
        c--;
        int A = dic[a], B = dic[b], C = dic[c];
        int lAB = lca.lca(A,B);
        int lBC = lca.lca(B,C);
        int lAC = lca.lca(A,C);
        bool ok = d(A,B,lAB,dist) + d(B,C,lBC,dist) == d(A,C,lAC,dist);
        cout << (ok ? "OK" : "NG") << endl;
    }
}