UnKoder #01 B Colorful Cards
問題
方針
あるカードの表が $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");
}
}