51nod 1515 明辨是非 并查集+set维护相等与不等关系
2024-10-21 12:38:58
考试时先拿vector瞎搞不等信息,又没离散化,结果好像MLE;后来想起课上讲过用set维护,就开始瞎搞迭代器。。。QWQ我太菜了。。
用并查集维护相等信息,用set记录不相等的信息:
如果要求变量不等,若不和并查集矛盾,就拿set互相记录一下,YES;矛盾就NO
如果要求变量相等,
1.x记录的不等的变量中有y,说明矛盾,NO
2.若祖先不等,那就合并两个变量所在的并查集(合并两个并查集的祖先),size大的并到小的上,set暴力转移集合不相等的信息,YES
否则YES
#include<cstdio>
#include<iostream>
#include<map>
#include<set>
#define R register int
using namespace std;
int n,cnt;
set<int> s[];
map<int,int>mp;
int fa[];
inline int g() {
R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;
do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;
}
int getf(int x) {return x==fa[x]?x:fa[x]=getf(fa[x]);}
signed main() {
n=g(); for(R i=;i<=n*+;++i) fa[i]=i;
for(R i=;i<=n;++i) {
R x=g(),y=g(),p=g();
if(mp[x]) x=mp[x]; else x=mp[x]=++cnt;
if(mp[y]) y=mp[y]; else y=mp[y]=++cnt;
x=getf(x),y=getf(y); if(s[x].size()<s[y].size()) swap(x,y);
if(p&) {
if(s[x].count(y)) putchar('N'),putchar('O'),putchar('\n');
else if(x!=y) { fa[y]=x;
for(set<int>::iterator it=s[y].begin();it!=s[y].end();it++)
s[*it].insert(x),s[x].insert(*it);
putchar('Y'),putchar('E'),putchar('S'),putchar('\n');
} else putchar('Y'),putchar('E'),putchar('S'),putchar('\n');
} else {
if(x==y) putchar('N'),putchar('O'),putchar('\n');
else s[x].insert(y),s[y].insert(x),
putchar('Y'),putchar('E'),putchar('S'),putchar('\n');
}
}
}
2019.04.11
最新文章
- mac php环境启动
- ABP理论学习之导航(Navigation)
- selenium如何分别启动IE、firefox、chrome浏览器
- input框颜色修该
- Effective C++ 学习笔记[2]
- [MySql] - 解决部署的服务器没有安装MySql Connector
- html系列教程--input label
- Jenkins Maven打包出错异常的解决方法
- javascript每日一练(二)——javascript(函数,数组)
- 在Xshell中上传下载文件到本地(linux中从多次ssh登录的dbserver里面的文件夹)
- 关于pagerank算法的一点点总结
- Python数据分析流程
- Hive:子查询
- mongodb副本集原理及部署记录
- 问题记录2019-03-06(todo)
- 链接错误:multiple definition of &#39;xxx&#39; 问题解决及其原理
- 1013 C. Photo of The Sky
- mac下编译cpu only caffe并用xCode建caffe工程
- python 游戏(龙的国度)
- mac上怎么安装dmg