【题目链接】:http://codeforces.com/contest/776/problem/D

【题意】



每个门严格由两个开关控制;

按一下开关,这个开关所控制的门都会改变状态;

问你能不能使所有的门都打开(同时);

【题解】

/*

    对于每个门,

    有两个开关连接着它;

    用一条边连接这两个开关

    则如果这个门的状态是关的,

    则这条边的边权为1

    表示它们俩的颜色不能一样;

    (也即这两个开关只能改变一个)

    也即要1开1关;

    如果这个门的状态是开的

    则这条边的边权为0；

    表示它们俩的颜色相同;

    即同时开或同时关.

    然后做一个二分图染色

    可以就是YES否则NO

    也就是说把开关看成节点,门看成边,根据边来确定这条边的两端的节点的颜色是一样还是不同;

*/

【完整代码】

#include <iostream>

#include <vector>

#include <cstdio>

#include <cstdlib>

#define rei(x) cin >> x

#define rep1(i,x,y) for (int i = x;i <= y;i++)

using namespace std;

const int N = 2e5 + 100;

int n, m, a[N],color[N];

vector <int> g1[N],g[N],w[N];

void dfs(int x, int c)

{

    color[x] = c;

    int len = g[x].size();

    rep1(i, 0, len - 1)

    {

        int y = g[x][i];

        int ju = w[x][i];

        if (color[y] != 0)

        {

            if (ju == 1 && color[y] == color[x])

            {

                puts("NO");

                exit(0);

            }

            if (ju == 0 && color[y] != color[x])

            {

                puts("NO");

                exit(0);

            }

        }

        else

            if (ju == 0)

                dfs(y, c);

            else

                dfs(y, 3 - c);

    }

}

int main()

{

    //freopen("D:\\rush.txt", "r", stdin);

    rei(n),rei(m);

    rep1(i, 1, n)

        rei(a[i]);

    rep1(i, 1, m)

    {

        int num;

        rei(num);

        rep1(j, 1, num)

        {

            int x;

            cin >> x;

            g1[x].push_back(n + i);

            g1[n + i].push_back(x);

        }

    }

    rep1(i, 1, n)

    {

        int y1 = g1[i][0], y2 = g1[i][1];

        int bian = 1 - a[i];

        g[y1].push_back(y2), g[y2].push_back(y1);

        w[y1].push_back(bian),w[y2].push_back(bian);

    }

    rep1(i,n+1,n+m)

        if (color[i] == 0)

            dfs(i, 1);

    puts("YES");

    return 0;

}