ICM Technex 2017 and Codeforces Round #400 (Div. 1 + Div. 2, combined) D. The Door Problem

ICM Technex 2017 and Codeforces Round #400 (Div. 1 + Div. 2, combined) D. The Door Problem

Problem - D - Codeforces

2SATの問題。

ドアがn個あって、それぞれのドアはそれぞれちょうど2個の異なるスイッチによって操作でき、スイッチは動かすと状態が反転する。1と0からなる最初の状態と、各ドアとスイッチの関係が与えられるので、すべての状態を1にできるかを判定する問題。スイッチに関する2SATが思いつき、あるドアを操作するためのスイッチは2個と決まっているので、各ドアについて、どのスイッチが対応しているかのペアについて、グラフを作る。

i番目のスイッチを押さない <=> x[i] = true

とし、あるドアに対するスイッチをi, j番目とすると、最初の状態が1ならば、2回または0回操作をしなければならないので、x[i] => x[j], not x[i] => not x[j]、そしてこれらの逆、を辺として繋ぐ。最初の状態が0ならば、1回の操作をしなければならないので、x[i] => not x[j], not x[i] => x[j]、これらの逆、を繋ぐ。あとはトポロジカルソートを見て終わり。アリ本のように一旦論理和をとるやり方は、意味わかるけれど、直感的に書けなくてわかりにくいと思った。

#include "bits/stdc++.h"
using namespace std;
#define rep(i, n)             for (int (i) = 0; (i) < (int)(n); (i)++)

int V;
vector<int> g[1010101];
vector<int> rg[1010101];
vector<int> order;
bool used[1010101];
int cmp[1010101];

void add_edge(int from, int to) {
        g[from].push_back(to);
        rg[to].push_back(from);
}
void dfs(int v) {
        used[v] = true;
        for (auto i : g[v]) if (!used[i]) dfs(i);
        order.push_back(v);
}
void rdfs(int v, int k) {
        used[v] = true;
        cmp[v] = k;
        for (auto i : rg[v]) if (!used[i]) rdfs(i, k);
}
int StronglyConnectedComponent() {
        memset(used, 0, sizeof(used));
        order.clear();
        for (int i = 0; i < V; i ++) if (!used[i]) dfs(i);
        memset(used, 0, sizeof(used));
        int k = 0;
        for (int i = order.size() - 1; i >= 0; i --) if (!used[order[i]]) rdfs(order[i], k ++);
        return k;
}

signed main() { 
        int n, m;
        cin >> n >> m;
        V = 2 * m;
        vector<int> state(n);
        bool f = true;
        rep(i, n) cin >> state[i];
        vector<int> B[101010];
        rep(i, m) {
                int q;
                cin >> q;
                while (q --) {
                        int a;
                        cin >> a;
                        a --;
                        B[a].push_back(i); // a番目のドアはこのi番目のスイッチで操作できる
                }
        }
        rep(i, n) {
                int a = B[i][0]; //2個だけpush_backされていることが保証されている
                int b = B[i][1];
                if (state[i] == 1) {
                        add_edge(a, b);
                        add_edge(b, a);
                        add_edge(a + m, b + m);
                        add_edge(b + m, a + m);
                } else {
                        add_edge(a, b + m);
                        add_edge(b + m, a);
                        add_edge(a + m, b);
                        add_edge(b, a + m);
                }
        }
        StronglyConnectedComponent();
        rep(i, m) if (cmp[i] == cmp[i + m]) {
                cout << "NO" << endl;
                return 0;
        }
        cout << "YES" << endl;
        return 0;
}