很好的一道集合关系的题目，我比赛时用的是dfs，后来看到有人用并查集。
两种方法本质是一样的，但后者实现起来更方便，代码更简练。
代码语言：javascript复制/****************************************************
file name: cf.cpp
author: huangjipeng
creat time: 2014年09月21日 星期日 22时32分55秒
***************************************************/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ls (p<<1)
#define rs (ls|1)
#define mid ((tree[p].l tree[p].r)>>1)
#define MAXN 1
typedef long long ll;
int n,a,b;
int num[100005];
int set[100005];
map <int,int> mp;
int find(int x)
{
if(set[x]!=x)
set[x]=find(set[x]);
return set[x];
}
int main()
{
cin>>n>>a>>b;
for(int i=1;i<=n;i )
{
scanf("%d",&num[i]);
mp[num[i]]=i;
}
for(int i=1;i<=(n 2);i )
set[i]=i;
for(int i=1;i<=n;i )
{
if(mp[a-num[i]])//如果有这个数，那么把i和这个数的下表放在一个集合中
set[find(i)]=find(mp[a-num[i]]);
else
set[find(i)]=find(n 2);//否则i放到n 2集合中；
if(mp[b-num[i]])
set[find(i)]=find(mp[b-num[i]]);
else
set[find(i)]=find(n 1);//第二种情况，放到n 1集合中
}
if(find(n 1)==find(n 2))//如果n 1和n 2在同一集合中，说明存在元素两个集合都不属于
cout<<"NO"<<endl;
else
{
cout<<"YES"<<endl;
for(int i=1;i<=n;i )
{
cout<<(find(i)==find(n 2))<<" ";
}
cout<<endl;
}
return 0;
}
