集合问题（并查集）

链接：https://www.nowcoder.com/acm/contest/77/D
来源：牛客网

集合问题

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

给你a,b和n个数p[i]，问你如何分配这n个数给A,B集合，并且满足：

若x在集合A中，则a-x必须也在集合A中。

若x在集合B中，则b-x必须也在集合B中。

输入描述:

第一行 三个数 n a b  1<=n<=1e5  1<=a,b<=1e9
第二行 n个数 p1 p2 p3...pn 1<=pi<=1e9

输出描述:

如果可以恰好分开就输出第一行 YES
然后第二行输出 n个数 分别代表pi 是哪个集合的  0 代表是A集合 1代表是B 集合
不行就输出NO
放在哪个集合都可以的时候优先放B

示例1

输入

4 5 9
2 3 4 5

输出

YES
0 0 1 1

示例2

输入

3 3 4
1 2 4

输出

NO

 1 #include <iostream>
 2 #include <cstring>
 3 #include <string>
 4 #include <algorithm>
 5 #include <cstdio>
 6 #include <map>
 7 using namespace std;
 8 
 9 const int maxn = 1e5 + 7;
10 int n, A, B, fa[maxn], a[maxn];
11 map<int, int>mp;
12 void init() {
13     for (int i = 0; i <= n + 1; i++)
14         fa[i] = i;
15 }
16 int find(int x)
17 {
18     if (fa[x] == x)return x;
19     else return fa[x] = find(fa[x]);
20 }
21 void uni(int x, int y)
22 {
23     int px = find(x);
24     int py = find(y);
25     if (px == py)return;
26     else fa[px] = py;
27 }
28 int main() 
29 {
30     scanf("%d%d%d", &n, &A, &B);
31     int max1 = 0;
32     for (int i = 1; i <= n; i++)
33     {
34         scanf("%d", &a[i]);
35         mp[a[i]] = i;
36         max1 = max(max1, a[i]);
37     }
38     if (max1 >= max(A, B))
39     {
40         return printf("NO
"), 0;
41     }
42     else
43     {
44         init();
45         for (int i = 1; i <= n; i++)
46         {
47             if (mp[B - a[i]])//如果B-a[i]存在
48                 uni(i, mp[B - a[i]]);//就把（B-a[i]）数的序号和i合并在一起
49             else uni(i, 0);//否则放到和0一个集合（a）里去
50             if (mp[A - a[i]])
51                 uni(i, mp[A - a[i]]);
52             else uni(i, n + 1);
53         }
54         int af = find(0);
55         int bf = find(n + 1);
56         if (af == bf)//一个数两个集合里都必须有，产生矛盾
57         {
58             return printf("NO
"), 0;
59         }
60         else
61         {
62             printf("YES
");
63             for (int i = 1; i <= n; i++)
64             {
65                 if (i != 1)printf(" ");
66                 if (af == find(i))printf("0");
67                 else printf("1");
68             }
69             printf("
");
70         }
71     }
72     return 0;
73 }