AtCoder ABC 235 E - MST + 1 (水色, 500 点)

MST の理解が問われる面白い教育的問題！

• 問題へのリンク

問題概要

頂点数 、辺数 の連結な重み付き単純無向グラフ が与えられる。なお、各辺の重みはすべて互いに異なることが保証されている。

の最小全域木を とする (一意に定まることが示せる)。

このグラフに 個のクエリが与えられる。各クエリでは、2 頂点 と重み が与えられる。この重み は、元のグラフ のどの辺の重みとも異なることが保証される。

このグラフ に頂点 を結ぶ重み の辺 を追加してできるグラフ の最小全域木を とする (一意に定まることが示せる)。

が辺 を含むかどうかを判定せよ。

制約

• 
• 
• 

考えたこと

こういう問題大好き！

クエリ処理問題では、まず 1 つのクエリに対する問題が解けるかどうかを考えると良いことが多いと思う。

つまり、グラフ に対して 1 本の を追加することによって、最小全域木が変わるのかどうかを考えるのだ。

Kruskal 法を思い出そう。そうすると、「グラフ の 本の辺と を混ぜた 本の辺集合」に対して kruskal 法を適用したときに、辺 を追加しようとする段階において

---

• の両端点がすでに同じグループにあるとき： はグラフ の最小全域木にも採用されない (答えは "No")
• の両端点が異なるグループにあるとき： はグラフ の最小全域木には採用される (答えは "Yes")

---

ということがわかる。

クエリが 個あっても、結局すべてのクエリを先読みして、 本の辺に 本の辺を混ぜた 本の辺に対して Kruskal 法を適用することで解ける。

計算量は となる。

コード

#include <bits/stdc++.h>
using namespace std;

// Union-Find
struct UnionFind {
    // core member
    vector<int> par;

    // constructor
    UnionFind() { }
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    // core methods
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x), y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
    
    // debug
    friend ostream& operator << (ostream &s, UnionFind uf) {
        map<int, vector<int>> groups;
        for (int i = 0; i < uf.par.size(); ++i) {
            int r = uf.root(i);
            groups[r].push_back(i);
        }
        for (const auto &it : groups) {
            s << "group: ";
            for (auto v : it.second) s << v << " ";
            s << endl;
        }
        return s;
    }
};

struct Edge {
    int x, y, w, id;
    Edge() {}
    Edge(int x, int y, int w, int id) : x(x), y(y), w(w), id(id) {}
    friend bool operator < (const Edge &a, const Edge &b) { return a.w < b.w; }
};

int main() {
    int N, M, Q;
    cin >> N >> M >> Q;
    
    vector<Edge> edges;
    for (int i = 0; i < M + Q; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        --a, --b;
        edges.push_back(Edge(a, b, c, i));
    }
    sort(edges.begin(), edges.end());
    
    UnionFind uf(N);
    vector<bool> res(Q);
    for (const auto &e : edges) {
        if (e.id >= M) res[e.id - M] = !uf.same(e.x, e.y);
        else uf.merge(e.x, e.y);
    }
    
    for (int i = 0; i < Q; ++i) cout << (res[i] ? "Yes" : "No") << endl;
}