?

題意：

就是有n個(gè)人，m場PK,，每一場PK都保證了一個(gè)是good,，一個(gè)是bad，然后給了X個(gè)已經(jīng)知道的好人的編號和Y個(gè)已經(jīng)知道的壞人的編號,。然后問能否分成兩個(gè)陣營,。

看樣例：

給的OK能將1，2,，4,，5分成兩大塊,，但是2何去何從是未知的，所以是NO,。

下一個(gè),，2是good,，所以能分成兩大塊,。

思路：

1.利用染色的方法，看能否給已知的圖進(jìn)行染色,，不成功說明矛盾輸出no,。

2.如果可以染色，還要判斷給定的X個(gè)是否在同一個(gè)集合里,。

如果在同一個(gè)連通分量里我才判斷,。否則沒有影響。

也可以用種類并查集做,。

比賽的時(shí)候?qū)懥藗€(gè)假的二分染色,。好傷心啊。,。嚶嚶嚶,。。,。

具體看代碼：

#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");
        }
    }
 }

?