AtCoder Regular Contest 036 D - 偶数メートル

学校始まってだんだん解けなくなってきてますね…とりあえず1日2問目標にします。

問題:D: 偶数メートル - AtCoder Regular Contest 036 | AtCoder

解法:各頂点1つごとに2つずつ頂点を用意し,それぞれ赤色と青色とする。で,頂点aと頂点bの間に道を作る時,
・道の長さが偶数ならaとbの同じ色同士をそれぞれグループ化する
・道の長さが奇数ならaとbの異なる色同士をそれぞれグループ化する
結論を言うと,aとbの間が偶数の距離で結ばれるというのと,aとbの同じ色が同じグループに属することは同値である。なぜなら,まずaとbがつながってない時はaとbは同じグループでないのでOK。また,aとbがつながっているときは,同じ色でつながっているときは,赤->青->赤->青->赤->赤というように,色の遷移は偶数回存在しなければならない。これは,奇数の道を偶数回通ることに対応しているので同値であることが確認できる。
以下ソースコード

// unionFind
const int UNION_MAX = 200100;
class unionFind {
    int par[UNION_MAX];
    int Rank[UNION_MAX];
public:
    void init(int nn) {
        for (int i = 0; i <= nn; i++) {
            par[i] = i;
            Rank[i] = 0;
        }
    }
    int find(int x) {
        if (x == par[x]) return x;
        return par[x] = find(par[x]);
    }
    void unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return;
        if (Rank[x] < Rank[y]) {
            par[x] = y;
        } else {
            par[y] = x;
            if (Rank[x] == Rank[y]) Rank[x]++;
        }
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
};
 
unionFind uf;
 
int main() {
    int N, Q;
    cin >> N >> Q;
    uf.init(2*(N+10));
    while (Q--) {
        int w, x, y, z;
        cin >> w >> x >> y >> z;
        if (w == 1) {
            z = z%2;
            if (z == 0) {
                uf.unite(2*x, 2*y);
                uf.unite(2*x-1, 2*y-1);
            } else {
                uf.unite(2*x-1, 2*y);
                uf.unite(2*x, 2*y-1);
            }
        } else {
            if (uf.same(2*x, 2*y)) cout << "YES" << endl;
            else cout << "NO" << endl;
        }
    }
    return 0;
}