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.icode9.com/content-4-35551.html