题意：略（忙着准备文化课。。。明天期中考啊。。。。
思路：
正解就是染色，2-sat搞；
AC代码（虽然是错误的。。。数据水（过踏马的也行啊，起码打脸他啊！）
4 3 1 0
1 2
2 3
3 4
4
这个就挂了；#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX=1010;
const double q=(1+sqrt(5.0))/2.0;
const double eps=1e-100;
int n,m;
int v[MAX];
int a[MAX][MAX];
int main()
{
int t,i,j;
int x,y;
while(~scanf("%d%d%d%d",&n,&m,&x,&y))
{
int flag=0;
int b,c;
memset(a,0,sizeof(a));
memset(v,-1,sizeof(v));
for(i=0;i<m;i++)
{
scanf("%d%d",&b,&c);
a[b][c]=a[c][b]=1;
}
for(i=1;i<=x;i++)
{
scanf("%d",&b);
for(j=0;j<n;j++)
{
if(a[b][j])
{
if(v[j]==1)
flag=1;
v[j]=0;
}
}
v[b]=1;
}
for(i=1;i<=y;i++)
{
scanf("%d",&b);
for(j=0;j<n;j++)
{
if(a[b][j])
{
if(v[j]==0)
flag=1;
v[j]=1;
}
}
v[b]=0;
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(a[i][j])
{
if(v[i]==-1&&v[j]==-1)
{
v[i]=1;
v[j]=0;
}
else if(v[i]!=-1&&v[j]!=-1)
{
if(v[i]+v[j]!=1)
flag=1;
}
else if(v[i]!=-1)
{
v[j]=1-v[i];
}
else
v[i]=1-v[j];
}
}
}
for(i=1;i<=n;i++)
{
// printf("%d ",v[i]);
if(v[i]==-1)
flag=1;
}
// puts("");
if(flag)
printf("NO
");
else
printf("YES
");
}
return 0;
}
贴份应该正确的（escape
#include<bits/stdc++.h>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const int N=5*1e4+1000;
#define eps 1e-4
int co[10005];
int vis[10005];
vector<int>g[10005];
int dfs(int u)
{
int sz=g[u].size();
for(int i=0; i<sz; i++)
{
int v=g[u][i];
if(!co[v])
{
co[v]=!co[u];
if(!dfs(v))
return 0;
}
else if(co[u]==co[v])
{
return 0;
}
}
return 1;
}
int main()
{
int n,m,x,y;
while(cin>>n>>m>>x>>y)
{
for(int i=0; i<10005; i++)
g[i].clear();
if(n==1)
{
puts("NO");
continue;
}
for(int i=0; i<m; i++)
{
int xx,yy;
scanf("%d%d",&xx,&yy);
g[xx].push_back(yy);
}
memset(co,0,sizeof(co));
for(int i=0; i<x; i++)
{
int xx;
scanf("%d",&xx);
co[xx]=1;
// int sz=g[xx].size();
// for(int i=0; i<sz; i++)
// {
// int v=g[xx][i];
// co[v]=!co[xx];
// }
}
for(int i=0; i<y; i++)
{
int xx;
scanf("%d",&xx);
co[xx]=0;
// int sz=g[xx].size();
// for(int i=0; i<sz; i++)
// {
// int v=g[xx][i];
// co[v]=!co[xx];
// }
}
if(x==0&&y==0)
puts("NO");
else
{
int flag=1;
for(int i=1; i<=n; i++)
if(!dfs(i))
flag=0;
if(flag)
puts("YES");
else
puts("NO");
}
}
return 0;
}加强后的瞎搞（求hack
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX=1010;
const double q=(1+sqrt(5.0))/2.0;
const double eps=1e-100;
int n,m;
int v[MAX];
int a[MAX][MAX];
int main()
{
int t,i,j,k;
int x,y;
while(~scanf("%d%d%d%d",&n,&m,&x,&y))
{
int flag=0;
int b,c;
memset(a,0,sizeof(a));
memset(v,-1,sizeof(v));
for(i=0; i<m; i++)
{
scanf("%d%d",&b,&c);
a[b][c]=a[c][b]=1;
}
for(i=1; i<=x; i++)
{
scanf("%d",&b);
for(j=0; j<n; j++)
{
if(a[b][j])
{
if(v[j]==1)
flag=1;
v[j]=0;
}
}
v[b]=1;
}
for(i=1; i<=y; i++)
{
scanf("%d",&b);
for(j=0; j<n; j++)
{
if(a[b][j])
{
if(v[j]==0)
flag=1;
v[j]=1;
}
}
v[b]=0;
}
for(k=0; k<2; k++)
{
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
if(a[i][j])
{
if(v[i]==-1&&v[j]==-1&&k)
{
v[i]=1;
v[j]=0;
}
else if(v[i]!=-1&&v[j]!=-1)
{
if(v[i]+v[j]!=1)
flag=1;
}
else if(v[i]!=-1)
{
v[j]=1-v[i];
}
else if(v[j]!=-1)
v[i]=1-v[j];
}
}
}
}
for(i=1; i<=n; i++)
{
// printf("%d ",v[i]);
if(v[i]==-1)
flag=1;
}
// puts("");
if(flag)
printf("NO
");
else
printf("YES
");
}
return 0;
}
/*
6 5 0 0
1 2
2 3
3 4
3 1
5 6
6 5 0 0
1 2
2 3
3 4
4 1
5 6
4 3 1 0
1 2
2 3
3 4
4
*/