题目大意:给出n个变量互相的相等或不等关系,求这些关系是否矛盾

思路:把相等的变量加入并查集,不等的查询是否合法

eg:数据很大,离散化(然而我用的是map)

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<map>
using namespace std;
int fa[],n,sum[],tot,T;
map<int,int> old,tong;
struct node
{
int x,y,c;
}a[];
template<class T>void read(T &x)
{
x=;char ch=getchar();
while(ch<''||ch>'') ch=getchar();
while(ch>=''&&ch<=''){x=(x<<)+(x<<)+(ch^);ch=getchar();}
}
int find(int x)
{
int p=x,q;
while(x!=fa[x])
x=fa[x];
while(p!=x)
{
q=fa[p];
fa[p]=x;
p=q;
}
return x;
}
int main()
{
read(T);
while(T--)
{
old.clear();tong.clear();tot=;bool flag=;
read(n);
for(int i=;i<=n;i++)
{
read(a[i].x);read(a[i].y);read(a[i].c);
if(tong[a[i].x]==)
{
tong[a[i].x]=;
sum[++tot]=a[i].x;
}
if(tong[a[i].y]==)
{
tong[a[i].y]=;
sum[++tot]=a[i].y;
}
}
sort(sum+,sum++tot);
for(int i=;i<=tot;i++) old[sum[i]]=i;
for(int i=;i<=n;i++)
{
a[i].x=old[a[i].x];
a[i].y=old[a[i].y];
}
for(int i=;i<=tot;i++) fa[i]=i;
for(int i=;i<=n;i++)
{
int p=find(a[i].x),q=find(a[i].y);
if(a[i].c==&&p!=q) fa[p]=q;
if(a[i].c!=&&p==q){flag=;break;}
}
if(flag==){printf("NO\n");continue;}
for(int i=;i<=n;i++)
{
int p=find(a[i].x),q=find(a[i].y);
if(a[i].c==&&p!=q){flag=;break;}
if(a[i].c==&&p==q){flag=;break;}
}
if(flag==)printf("NO\n");
else printf("YES\n");
}
return ;
}

最新文章

  1. rdesktop的使用方法
  2. 20个优秀的 JavaScript 键盘事件处理库
  3. Apple Demo
  4. 锁定方式SDE中插入要素
  5. Photoshop:制作方块背景
  6. hdu 4192
  7. iOS流布局UICollectionView使用FlowLayout进行更灵活布局
  8. [Angular 2] Using events and refs
  9. Qt使用快捷键
  10. matplotlib中使用imshow绘制二维图
  11. lightoj 1038 Race to 1 Again
  12. Python自动化环境搭建
  13. 通过DNS传输后门来绕过杀软
  14. 解决VS2019中.net core WPF 暂时无法使用 Designer 的临时方法
  15. 石家庄地铁系统开发(java web版)(一)
  16. Currency Exchange POJ - 1860 (spfa判断正环)
  17. linux下 编译安装Mysql
  18. 文件操作命令(TYPE)
  19. mysql 关联查询技巧
  20. 【分享】Web前端开发第三方插件大全

热门文章

  1. 关于C/C++中求最大公约数和最小公倍数的算法
  2. node-log4js3.0.6配置
  3. ES6 扩展运算符 三点(...)
  4. 使用 Java 程序写文件时,记得要 flush()
  5. Mac os的使用
  6. js中 函数声明/函数表达式/匿名函数/箭头函数/立即执行函数
  7. postgresql数据库和mysql数据库的对比分析
  8. iframe 加载外部资源,显示隐藏loading,onload失效
  9. ubuntu下nodejs和npm的安装及升级
  10. vue的组件基础