codeforces 776D-The Door Problem 2-sat模板题

题意：有n个门和m个开关，每个门被两个开关控制。现给出控制关系与每个门当前状态，问能否让所有门全开

思路：2-sat模板题，用两个条件构成两种选择，当留个板子把。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<queue>
#include<vector>
#include<map>
using namespace std;
long long maxn=200005; 
vector<int>g[200005];
int a[200005];
struct TwoSAT
{
    int n;
    vector<int>G[400010];
    bool mark[400010];
    int S[400010], c;
    bool dfs(int x) {
        if(mark[x^1]) return false;
        if(mark[x]) return true;
        mark[x] = true;
        S[c++] = x;
        for(int i = 0; i < G[x].size(); i++)
            if(!dfs(G[x][i])) return false;
        return true;
    }
    void init(int n) {
        this->n = n;
        for(int i = 0; i < n * 2; i++) G[i].clear();
        memset(mark, false, sizeof(mark));
    }
    void add_clause(int x, int xval, int y, int yval) {
        x = x * 2 + xval;
        y = y * 2 + yval;
        G[x^1].push_back(y);
        G[y^1].push_back(x);
    }
    bool solve() {
        for(int i = 0; i < n * 2; i += 2)
            if(!mark[i] && !mark[i+1]) {
                c = 0;
                if(!dfs(i)) {
                    while(c > 0) mark[S[--c]] = false;
                    if(!dfs(i+1)) return false;
                }
            }
        return true;
    }
}solver;
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)scanf("%d",&a[i]);
	for(int i=0;i<m;i++)
	{
		int x;
		scanf("%d",&x);
		for(int j=1;j<=x;j++)
		{
			int u;
			scanf("%d",&u);
			u--;
			g[u].push_back(i);
		}
	}
	solver.init(m);
	for(int i=0;i<n;i++)
	{
		int u=g[i][0];
		int v=g[i][1];
		solver.add_clause(u,0,v,a[i]==1?1:0);
		solver.add_clause(u,1,v,a[i]==1?0:1);
	}
	if(solver.solve()==1)printf("YES\n");
	   else printf("NO\n");
	   return 0;
}