并查集水题

离散化之后直接并查集合并,在不等时判断两者是否在同一个集合內即可

注意排序

贴代码:

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
using namespace std;
map <int,int> M1,M2;
int tot=0;
int T,n;
struct Ques
{
int l,r,typ;
friend bool operator < (Ques a,Ques b)
{
return a.typ>b.typ;
}
}q[100005];
int f[200005];
int siz[200005];
int findf(int x)
{
return x==f[x]?x:f[x]=findf(f[x]);
}
void init()
{
M1.clear(),M2.clear(),tot=0;
for(int i=1;i<=2*n;i++)f[i]=i,siz[i]=1;
}
inline int read()
{
int f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int main()
{
T=read();
while(T--)
{
n=read();init();
for(int i=1;i<=n;i++)
{
q[i].l=read(),q[i].r=read(),q[i].typ=read();
M1[q[i].l]=M1[q[i].r]=1;
}
sort(q+1,q+n+1);
map <int,int>::iterator it;
for(it=M1.begin();it!=M1.end();it++)M2[it->first]=++tot;
for(int i=1;i<=n;i++)q[i].l=M2[q[i].l],q[i].r=M2[q[i].r];
bool fl=0;
for(int i=1;i<=n;i++)
{
int f1=findf(q[i].l),f2=findf(q[i].r);
if(q[i].typ==1&&f1!=f2)
{
if(siz[f1]>siz[f2])f[f2]=f1,siz[f1]+=siz[f2];
else f[f1]=f2,siz[f2]+=siz[f1];
}
else if(q[i].typ==0&&f1==f2){fl=1;break;}
}
if(fl)printf("NO\n");
else printf("YES\n");
}
return 0;
}

最新文章

  1. Excel替换应用
  2. user profile services提示&ldquo;BAIL: MMS(7116): sql.cpp(8490): 0x80231334 (The sql connection string has unsupported values.)&rdquo;解决办法
  3. Halcon学习标定助手
  4. SSAS数据挖掘算法简介
  5. Android完全退出应用程序,完美解决方案
  6. java 解析json的问题
  7. nodejs笔记2 --关于nodejs最新启动方式
  8. kendo ui grid选中行事件,获取combobox选择的值
  9. Cookie 和 Session的基本使用
  10. AngularJS进阶(二十二)实现时间选择插件
  11. 接口自动化:HttpClient + TestNG + Java(二) - 第一个接口测试:get请求
  12. java_爬虫_从腾讯视频播放界面爬取视频真实地址
  13. js模板引擎art-Template(以前的artTemplate)
  14. MATLAB的一些使用的快捷键整理
  15. React之父子组件传递和其它一些要点
  16. springboot系列二、springboot项目搭建
  17. django基础-02:虚拟环境
  18. win7,Ubuntu 12.04 双系统修改启动项顺序三方法
  19. redis 多实例 连接 加密码
  20. 《从零开始学Swift》学习笔记(Day67)——Cocoa Touch设计模式及应用之MVC模式

热门文章

  1. 继承方式创建线程(继承Thread类)
  2. java心形打印999
  3. web服务器应答状态代码(status)及其含义
  4. Python系统模块os.py和sys.py常用函数
  5. VKM4 批准功能对应 bapi
  6. android root app 无法umount
  7. 把pyecharts动图导入到PPT中
  8. Linux安装oracle jdk
  9. YOLO v6:一个硬件友好的目标检测算法
  10. django的注意事项