bzoj 4195
2024-10-22 10:50:05
并查集水题
离散化之后直接并查集合并,在不等时判断两者是否在同一个集合內即可
注意排序
贴代码:
#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;
}
最新文章
- Excel替换应用
- user profile services提示&ldquo;BAIL: MMS(7116): sql.cpp(8490): 0x80231334 (The sql connection string has unsupported values.)&rdquo;解决办法
- Halcon学习标定助手
- SSAS数据挖掘算法简介
- Android完全退出应用程序,完美解决方案
- java 解析json的问题
- nodejs笔记2 --关于nodejs最新启动方式
- kendo ui grid选中行事件,获取combobox选择的值
- Cookie 和 Session的基本使用
- AngularJS进阶(二十二)实现时间选择插件
- 接口自动化:HttpClient + TestNG + Java(二) - 第一个接口测试:get请求
- java_爬虫_从腾讯视频播放界面爬取视频真实地址
- js模板引擎art-Template(以前的artTemplate)
- MATLAB的一些使用的快捷键整理
- React之父子组件传递和其它一些要点
- springboot系列二、springboot项目搭建
- django基础-02:虚拟环境
- win7,Ubuntu 12.04 双系统修改启动项顺序三方法
- redis 多实例 连接 加密码
- 《从零开始学Swift》学习笔记(Day67)——Cocoa Touch设计模式及应用之MVC模式