HDOJ 5971 Wrestling Match【2016大连现场】【dfs二分染色】

现场赛的时候，自己一个人乱搞了一发，其实题意是看懂了的，判断是对的。。。。

就是前期太SB，导致中期后期不自信，这是最大最大的问题

说下题意：

n个点，m条边。x个好人，y个坏人，其中x+y<=n

好人相连的人一定是坏人，坏人相连的点一定是好人

问：我们是否可以给每个人定好坏的性质，使得既不矛盾，又不会出现某个人没有好坏身份的情况

样例：

5 5 0 0

5 1

1 2

2 3

3 4

4 5

会发现未知信息成了一个环形。

假如我们定义1号为好人，那么3号好人，2号和4号是坏人；但是现在，因为4号坏人，所以5号好人；又因为1号好人，所以5号坏人

所以出现了矛盾啊。说明这个图是NO的

这个题：就是基本的dfs染色啊！

那么赛场上为什么不会呢？因为，没有提前预处理x和y。

因为这个x和y，是提前把好人和坏人都定义好了，所以他们先要去图上标记好

dfs（u）的时候，判断每个u的相邻节点v

v如果与u颜色相同，那么返回错误信息

v如果与u颜色相反，那么说明之前已经来过这个点，返回

v如果没有颜色，给v染上与u相反的颜色，然后继续dfs

然后呢，题目的样例告诉我们一个小细节：

去搜索的时候，需要对每个点进行标记（它在题目中是否出现过）

第二组样例是2没有出现过，但是在x和y中，可以直接标记为好人；但是第一组少了2这个点的好坏信息

代码如下：

#include<bits/stdc++.h>
using namespace std;

const int maxn=1050;
const int maxm=20050;
struct node{
    int v,nxt;
}edge[maxm];
int col[maxn];
int head[maxn];
int n,m,x,y,tot;
bool flag;
bool vis[maxn];

void init(){
    memset(head,-1,sizeof(head));
    memset(col,-1,sizeof(col));
    memset(vis,false,sizeof(vis));
    tot=0;
    flag=true;
}

void addedge(int u,int v){
    edge[tot].v=v;
    edge[tot].nxt=head[u];
    head[u]=tot++;
}

void dfs(int x,int color){
    if (col[x]==color) return;
    else if (col[x]==1-color){
        flag=false;
        return;
    }
    else{
        col[x]=color;
        for(int i=head[x];i!=-1;i=edge[i].nxt){
            int v=edge[i].v;
            dfs(v,1-color);
        }
    }
}

int main(){
    //freopen("input.txt","r",stdin);
    int u,v;
    while(scanf("%d%d%d%d",&n,&m,&x,&y)!=EOF){
        init();
        while(m--){
            scanf("%d%d",&u,&v);
            vis[u]=vis[v]=true;
            addedge(u,v);
            addedge(v,u);
        }
        for(int i=1;i<=x;i++){
            scanf("%d",&u);
            vis[u]=true;
            if (flag) dfs(u,1);
        }
        for(int i=1;i<=y;i++){
            scanf("%d",&v);
            vis[v]=true;
            if (flag) dfs(v,0);
        }
        if (flag){
            for(int i=1;i<=n;i++)
                if (col[i]==-1&&vis[i]) dfs(i,1);
            for(int i=1;i<=n;i++)
                if (col[i]==-1){
                    flag=false;
                    break;
                }
        }
        printf("%s\n",flag?"YES":"NO");
    }
    return 0;
}