hdu5971—Wrestling Match（二分图染色 并查集）

 

题意：

就是有n个人，m场PK，每一场PK都保证了一个是good，一个是bad，然后给了X个已经知道的好人的编号和Y个已经知道的坏人的编号。然后问能否分成两个阵营。

看样例：

给的OK能将1，2，4，5分成两大块，但是2何去何从是未知的，所以是NO。

下一个，2是good，所以能分成两大块。

思路：

1.利用染色的方法，看能否给已知的图进行染色，不成功说明矛盾输出no。

2.如果可以染色，还要判断给定的X个是否在同一个集合里。

如果在同一个连通分量里我才判断。否则没有影响。

也可以用种类并查集做。

比赛的时候写了个假的二分染色。好伤心啊。。嘤嘤嘤。。。

具体看代码：

#include<bits/stdc  .h>
using namespace std;
const int MAXN=20010;
 vector<int> graph[MAXN];
int color[MAXN];
int VIS[MAXN];
bool DFS(int u)
{
    int len=graph[u].size();
    for(int j=0;j<len;j  )
    {
        int v=graph[u][j];
        if(color[v]==0)
        {
            color[v]=3-color[u];
            if(!DFS(v))
                return false;
        }
    else if(color[u]==color[v])
        return false;
    }
    return true;
}
int pre[MAXN];
int Find(int a)
{
    return pre[a]=(a==pre[a]?a:Find(pre[a]));
}
void Merge(int x,int y)
{
    int dx = Find(x), dy = Find(y);

    pre[dx] = dy;
}
int main()
{
    int t,n,m,a,b,X,Y;
    while(scanf("%d%d%d%d",&n,&m,&X,&Y)!=EOF)
    {
        memset(graph,0,sizeof(graph));
        memset(VIS,0,sizeof(VIS));
        for(int i=1;i<=n;i  ){
            pre[i]=i;
        }
        for(int i=1;i<=m;i  )
        {
            scanf("%d%d",&a,&b);
            graph[a].push_back(b);
            graph[b].push_back(a);
            VIS[a]=1;
            VIS[b]=1;
            Merge(a,b);
        }
        memset(color,0,sizeof(color));
        int flag=true;
        for(int i=1;i<=n;i  )
        {
            if(color[i]==0)
            {
                if(!DFS(i))
                {
                    color[i]=1;
                    flag=false;
                    break;
                }
            }
        }
        int x;
        for(int i=1;i<=X;i  ){
            scanf("%d",&x);
            VIS[x]=1;
        }
        for(int i=1;i<=Y;i  ){
            scanf("%d",&x);
            VIS[x]=1;
        }
        int biaozhi=0;
        if(flag)///是二分图
        {
            for(int i=2;i<=X;i  ){
                if(Find(i)==Find(i-1)){
                    if( color[i]!=color[i-1] ){
                        printf("NO\n");
                        biaozhi=1;
                        break;
                    }
                }
            }
            if(biaozhi)
                continue;
             for(int i=2;i<=Y;i  ){
                if(Find(i)==Find(i-1)){
                    if( color[i]!=color[i-1] ){
                        printf("NO\n");
                        biaozhi=1;
                        break;
                    }
                }
            }
            if(biaozhi)
                continue;
            for(int i=1;i<=n;i  ){
                if(!VIS[i])
                {
                    printf("NO\n");
                    biaozhi=1;
                }
            }
            if(biaozhi==0){
                printf("YES\n");
            }
        }
        else
        {
            printf("NO\n");
        }
    }
 }

 

来源：http://www./content-4-35551.html