首页 > 代码库 > 51nod 1515 明辨是非 并查集 + set + 启发式合并
51nod 1515 明辨是非 并查集 + set + 启发式合并
给n组操作，每组操作形式为x y p。
当p为1时，如果第x变量和第y个变量可以相等，则输出YES，并限制他们相等；否则输出NO，并忽略此次操作。
当p为0时，如果第x变量和第y个变量可以不相等，则输出YES，并限制他们不相等 ；否则输出NO，并忽略此次操作。
Input
输入一个数n表示操作的次数(n<=1*10^5)接下来n行每行三个数x,y,p（x,y<=1*10^8,p=0 or 1）Output
对于n行操作，分别输出n行YES或者NOInput示例
31 2 11 3 12 3 0Output示例
YESYESNO
刚开始只是用了一个并查集，维护每一个节点和其父节点的关系，相等或者不相等，
但是这样是不对的，比如a != b,c ！= b,但是这个时候a和c 的关系不能确定。
改为：
用并查集维护相等的关系，每一个并查集的父节点再维护一个set，放着所有确定了和这个
集合不相等的集合的父节点，然后合并的时候启发式合并一下。
代码：
1 2 //File Name: nod1515.cpp 3 //Author: long 4 //Mail: 736726758@qq.com 5 //Created Time: 2016年09月16日 星期五 23时01分02秒 6 7 #include <stdio.h> 8 #include <string.h> 9 #include <algorithm>10 #include <iostream>11 #include <set>12 #include <map>13 using namespace std;14 const int MAXN = 100000 + 10;15 int fa[MAXN];16 map<int,int> rem;17 set<int> dis[MAXN];18 struct Query{19 int x,y,p;20 }que[MAXN];21 int find_fa(int x){22 if(fa[x] == x) return x;23 return fa[x] = find_fa(fa[x]);24 }25 void union_to(int x,int y){26 fa[y] = x;27 set<int>::iterator it;28 for(it=dis[y].begin();it!=dis[y].end();it++){29 int v = *it;30 dis[v].erase(y);31 dis[v].insert(x);32 dis[x].insert(v);33 }34 dis[y].clear();35 }36 void _union(int x,int y){37 if(dis[x].size() >= dis[y].size()) union_to(x,y);38 else union_to(y,x);39 }40 void solve(int n,int tot){41 for(int i=1;i<=n;i++){42 que[i].x = rem[que[i].x];43 que[i].y = rem[que[i].y];44 }45 for(int i=1;i<=tot;i++){46 fa[i] = i;47 dis[i].clear();48 }49 for(int i=1;i<=n;i++){50 int x = que[i].x,y = que[i].y,p = que[i].p;51 int fax = find_fa(x);52 int fay = find_fa(y);53 if(fax == fay){54 if(p) puts("YES");55 else puts("NO");56 }57 else{58 if(p){59 if(dis[fax].find(fay) != dis[fax].end()) puts("NO");60 else{61 puts("YES");62 _union(fax,fay);63 }64 }65 else{66 puts("YES");67 dis[fax].insert(fay);68 dis[fay].insert(fax);69 }70 }71 }72 }73 int main(){74 int n;75 while(~scanf("%d",&n)){76 int tot = 0;77 rem.clear();78 for(int i=1;i<=n;i++){79 scanf("%d %d %d",&que[i].x,&que[i].y,&que[i].p);80 if(!rem[que[i].x]) rem[que[i].x] = ++tot;81 if(!rem[que[i].y]) rem[que[i].y] = ++tot;82 }83 solve(n,tot);84 }85 return 0;86 }
51nod 1515 明辨是非 并查集 + set + 启发式合并
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。