SRM505 Div1 Easy - RectangleArea

問題

 H \times Wの長方形をN - 1本の横棒、 M - 1本の縦棒を用いてN \times M個の長方形に分割する。いくらかの小長方形の面積がわかっているとき、全体の面積を特定するために知る必要がある小長方形の個数を求めよ。

解法

 この記事にある通りunion find。

反省

 何か共有しているかどうかを見るんだろうなというところでunion-findが思いつかなかった。いろいろググって自分の考えていた方法と近いものを見つけてようやく理解できた。

 メタ読みばかりしてしまうのでTopCoderのレベル感に慣れないと全然問題が解けない。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = long long;

class RectangleArea {
public:
    int minimumQueries(vector <string> known) {
        const int N = (int)known.size();
        const int M = (int)known.front().size();
        initNodes(N + M);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (known[i][j] == 'Y') {
                    unite(i, N + j);
                }
            }
        }

        int ans = -1;
        for (int i = 0; i < N + M; i++) {
            if (parent[i] < 0) {
                ans++;
            }
        }

        return ans;
    }
private:
    vector<int> parent;
    void initNodes(int num) {
        parent.resize(num);
        for (auto& node : parent) {
            node = -1;
        }
    }
    int root(int x) {
        return (parent[x] < 0 ? x : parent[x] = root(parent[x]));
    }
    void unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x != y) {
            parent[y] = x;
        }
    }
};