UnKoder #01 B Colorful Cards

2015/04/15 (Wed) hackerrank UnKoder Union-Find

問題

日本語があります

方針

あるカードの表が $x$ で裏が $y$ のとき、 別のカードで $x$ と $y$ が含まれているものは必ず同時に裏返す必要があります。 このような繋がりによってカードのグループを作っていき、 最終的に全てのグループの大きさが $K$ 以下であれば Yes です。

実装

struct UnionFind {
    vector<int> par;
    int cnt;
    UnionFind(int size_) : par(size_, -1), cnt(size_) { }
    bool set(int x, int y) {
        x = find(x); y = find(y);
        if (x != y) {
            if (par[y] < par[x]) swap(x, y);
            par[x] += par[y]; par[y] = x;
            cnt--;
        }
        return x != y;
    }
    bool get(int x, int y) {
        return find(x) == find(y);
    }
    int find(int x) {
        return par[x] < 0 ? x : par[x] = find(par[x]);
    }
    int size(int x) {
        return -par[find(x)];
    }
    int size() {
        return cnt;
    }
};


int main(){
    int N,K;
    while(cin >> N >> K){
        UnionFind t(N);
        int a[60], b[60];
        rep(i,N) cin >> a[i];
        rep(i,N) cin >> b[i];
        rep(i,N){
            t.set(a[i]-1,b[i]-1);
        }
        bool ok = true;
        rep(i,N){
            ok &= t.size(i) <= K;
        }
        puts(ok ? "Yes" : "No");
    }
}