Flipping Matrix [CSAcademy #66 D]

https://csacademy.com/contest/round-66/task/flipping-matrix/

N×Nのバイナリ行列がある。
以下のクエリを行う。
「R x y」x行目とy行目をスワップする
「C x y」x列目とy列目をスワップする
N回以下、このクエリを行って、主対角線全てを1にできるか判定せよ。
出来るならクエリも示せ。

前提知識

• 二部マッチング
• UnionFind

解法

まずクエリを最小回数に抑える必要が無いというのが重要な所。
あとは、クエリは2種類あるが1種類で実現可能であるということ。
二番目は根拠が無いのだが、経験的によくある。
　
まず実現可能かであるが、これは二部マッチングでできる。
もし実現可能であれば、スワップを構築するだけだが、移動先に遷移を貼るとすると、これはN頂点N辺のグラフとなるので、連結成分毎にまとめて、上手くスワップを作ればいい。

int N, X[1010][1010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(y, 0, N) rep(x, 0, N) cin >> X[y][x];

    BipartiteMatching bm(N, N);
    rep(y, 0, N) {
        rep(x, 0, N) if (X[y][x] == 1) bm.add_edge(y, x);
    }

    if (bm.match() != N) {
        printf("-1\n");
        return;
    }

    UnionFind uf(N);
    rep(i, 0, N) uf(i, bm.whois(i));
    map<int, vector<int>> cmp;
    rep(i, 0, N) cmp[uf[i]].push_back(i);
    
    fore(p, cmp) {
        auto &v = p.second;
        if (v.size() == 1) continue;

        int st = v[0], cur = v[0];
        while (bm.whois(cur) != st) {
            int a = cur;
            int b = bm.whois(cur);
            printf("C %d %d\n", a + 1, b + 1);
            cur = b;
        }
    }
}