并查集做题总结

CF 469B

构造出两个节点n+1,n+2来存放A集合和B集合中的数据，显然一个合理的分配不会使得一个元素既在A里面，也在B里面。而由于每一个元素都要去分配，如果a-x没有那它就得在B里面（和n+2合并），同理对于b-x没有的情况。最后根据它和n+1的祖宗是不是同一个来判断是属于哪个集合。

//CodeForces 469D #include <cstdio> #include <cstring> #include <string> #include <map> #include <iostream> #include <cmath> #include <vector> #include <set> #include <algorithm> typedef long long ll; #define rep(i,a,b) for (int i = (a); i <= (b); ++i) #define rep(i,a,b) for (int i = (a); i <= (b); ++i) using namespace std; const int N = 200010; int ans, n ,x, y, a[N], b[N], f[N]; map<int,int> mp; int find(int k){if (f[k]==k)return k;elsereturn find(f[k]); } void merge(int x,int y){int fx, fy;fx = find(x);fy = find(y);if (fx < fy)f[fy] = fx;elsef[fx] = fy; } int main() {cin >> n >> x >> y;rep (i, 1, n){scanf("%d",&a[i]);mp[a[i]] = i;}rep (i,1,n+2){f[i] = i;}rep (i, 1, n){if (mp.count(x-a[i])==1){//如果存在都在A集合，那么这两个节点合并merge(i,mp[x-a[i]]);}else{//否则合并到n+1(B)集合里merge(i,n+1);}if (mp.count(y-a[i])==1){//都在B集合merge(i,mp[y-a[i]]);}else{merge(i,n+2);//合并到n+2（A）集合里}}if (find(n+1) == find(n+2)){//如果成立则这两个点应该不会冲突puts("NO");return 0;}puts("YES");int anc = find(n+1);rep (i,1,n){//cout << find(i) << endl;cout << (find(i)==anc) << " ";}puts("");return 0; }

 

转载于:https://www.cnblogs.com/ohazyi/p/7018454.html

总结

以上是生活随笔为你收集整理的并查集做题总结的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。