洛谷【P1955 [NOI2015] 程序自动分析】
反思：
- 这道题一眼就是并查集 但是数据太大 mle和re都是有可能的
- 我看了题解才知道是离散化数组加并查集
- 离散化再两个月前我觉得好难啊 那道题跟本看不懂 现在觉得还行
离散化思路：
需要一个离散记录数组----ls[N]用来记录下出现的数
步骤：
先存数组
排序
unique去重得长度
然后用lower_bound迭代器赋值
unique用法是int len=unique(li+1,li+1+cnt)-li-1; （start,start+总长度）-start 得到最后长度’ne[i].a=lower_bound(li+1,li+len+1,ne[i].a)-li-1;
lower_bound的用法：返回大于等于ne[i].a的最早位置
写法跟上面类似：（start，start+长度，数大小）-start
题目思路：
先离散化缩小区间 再进行并查集操作 结构体要排序 按0和1排 1在前面 对于循环中是0的进行判断祖先节点是否相等 相等就矛盾 打印no 直到循环结束flag还为1的话就打印yes
ac代码
#include<bits/stdc++.h>
using namespace std;
//离散化步骤：排序，去重，赋值
const int N=300000;
int li[N],fa[N];
void first(int x){for(int i=1;i<=x;i++) fa[i]=i;
}
int find(int x){if(fa[x]==x) return x;fa[x]=find(fa[x]);return fa[x];
}
void merge(int a,int b){int t1=find(a),t2=find(b);fa[t1]=t2;
}
struct node{int a,b,c;
}ne[100010];
bool cmp(node a,node b){return a.c>b.c;
}
int main(){int n;cin>>n;while(n--){memset(fa,0,sizeof(fa));memset(li,0,sizeof(li));int t;cin>>t;int cnt=0;for(int i=1;i<=t;i++){int x,y,z;cin>>x>>y>>z;ne[i]={x,y,z};li[++cnt]=x,li[++cnt]=y;//输入完成 开始离散}sort(li+1,li+cnt+1);//从1开始int len=unique(li+1,li+1+cnt)-li-1;// cout<<len<<endl;//len是用来 loow_bound里面的和初始化first的for(int i=1;i<=t;i++){//离散赋值ne[i].a=lower_bound(li+1,li+len+1,ne[i].a)-li-1;ne[i].b=lower_bound(li+1,li+len+1,ne[i].b)-li-1;}// for(int i=1;i<=t;i++){// //离散赋值// // ne[i].a=lower_bound(li+1,li+cnt+1,ne[i].a)-li-1;// // ne[i].b=lower_bound(li+1,li+cnt+1,ne[i].b)-li-1;// cout<<ne[i].a<<" "<<ne[i].b<<endl;// }first(len);bool flag=1;sort(ne+1,ne+1+t,cmp);// for(int i=1;i<=t;i++){// cout<<ne[i].a<<" "<<ne[i].b<<" "<<ne[i].c<<endl;// }'for(int i=1;i<=t;i++){if(ne[i].c==1){merge(ne[i].a,ne[i].b);}else if(ne[i].c==0){if(find(ne[i].a)==find(ne[i].b)){cout<<"NO"<<endl;flag=0;break;}}}if(flag==1) cout<<"YES"<<endl;}return 0;
}