#include <iostream>
#include <vector>
#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);
#define REP(i, n) for(int i=0;i<int(n);++i)
class UnionFind {
private:
std::vector<int> parent;
std::vector<int> height;
std::vector<int> m_size;
public:
UnionFind(int size_) : parent(size_), height(size_, 0), m_size(size_, 1) {
REP(i, size_) {
parent[i] = i;
}
}
void init(int size_) {
parent.resize(size_);
height.resize(size_, 0);
m_size.resize(size_, 0);
REP(i, size_) {
parent[i] = i;
}
}
int find(int x) {
if (parent[x] == x) {
return x;
}
return parent[x] = find(parent[x]);
}
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
int t = size(x) + size(y);
m_size[x] = m_size[y] = t;
if (height[x] < height[y]) parent[x] = y;
else parent[y] = x;
if (height[x] == height[y]) ++height[x];
}
bool same(int x, int y) {
return find(x) == find(y);
}
int size(int x) {
if (parent[x] == x) {
return m_size[x];
}
return size(parent[x] = find(parent[x]));
}
};
signed main() {
INIT;
int n, m;
std::cin >> n >> m;
std::vector<int> r(n);
REP(i, n) {
std::cin >> r[i];
}
std::vector<std::vector<int>> d(m);
REP(i, m) {
int x;
std::cin >> x;
REP(j, x) {
int d_input;
std::cin >> d_input;
d[i].emplace_back(d_input);
}
}
std::vector<std::vector<int>> swch(n);
REP(i, m) REP(j, d[i].size()) {
swch[d[i][j] - 1].emplace_back(i);
}
UnionFind uf(m * 2);
REP(i, n) {
if (r[i] == 1) {
uf.unite(swch[i][0] , swch[i][1] );
uf.unite(swch[i][0] + m, swch[i][1] + m);
}
else {
uf.unite(swch[i][0] , swch[i][1] + m);
uf.unite(swch[i][0] + m, swch[i][1] );
}
}
REP(i, m) {
if (uf.same(i, i + m)) {
std::cout << "NO\n";
return 0;
}
}
std::cout << "YES\n";
return 0;
}
前半は素集合森の定義です。ここでの説明は省略します。
std::vector<std::vector<int>> swch(n);
REP(i, m) REP(j, d[i].size()) {
swch[d[i][j] - 1].emplace_back(i);
}
ここでの
は、各ドアが繋がるスイッチ2つを指す配列です。
UnionFind uf(m * 2);
REP(i, n) {
if (r[i] == 1) {
uf.unite(swch[i][0] , swch[i][1] );
uf.unite(swch[i][0] + m, swch[i][1] + m);
}
else {
uf.unite(swch[i][0] , swch[i][1] + m);
uf.unite(swch[i][0] + m, swch[i][1] );
}
}
この部分では、実際に問題を解くためのグラフを構築しています。
ここで、グラフ上での頂点番号について、「スイッチ
がオフである」という頂点の番号は
とするようにしています。

図は
であるときですが、こうするとどのスイッチに対しても、オンとオフで頂点番号の差がちょうど
となっていることが分かりますね。
頂点の繋げ方は、上に述べた通りです。
REP(i, m) {
if (uf.same(i, i + m)) {
std::cout << "NO\n";
return 0;
}
}
std::cout << "YES\n";
return 0;
最後に、あるスイッチ
がオンである状態とオフである状態が同じ連結成分に属していないかを調べます。
一つでも属していることが分かれば、条件を満たす組み合わせが存在しないため、答えは
となります。
全て別の連結成分に属していれば、答えは
となります。