网站建设行业企业排名,做网站的需要什么资质证明,wordpress用户注册邮件验证码,百度公司怎么样反思#xff1a;
这道题一眼就是并查集 但是数据太大 mle和re都是有可能的我看了题解才知道是离散化数组加并查集离散化再两个月前我觉得好难啊 那道题跟本看不懂 现在觉得还行
离散化思路#xff1a;
需要一个离散记录数组----ls[N]用来记录下出现的数
步骤#xff1a;
…反思
这道题一眼就是并查集 但是数据太大 mle和re都是有可能的我看了题解才知道是离散化数组加并查集离散化再两个月前我觉得好难啊 那道题跟本看不懂 现在觉得还行
离散化思路
需要一个离散记录数组----ls[N]用来记录下出现的数
步骤
先存数组
排序
unique去重得长度
然后用lower_bound迭代器赋值
unique用法是int lenunique(li1,li1cnt)-li-1; start,start总长度-start 得到最后长度’ne[i].alower_bound(li1,lilen1,ne[i].a)-li-1;
lower_bound的用法返回大于等于ne[i].a的最早位置
写法跟上面类似startstart长度数大小-start题目思路
先离散化缩小区间 再进行并查集操作 结构体要排序 按0和1排 1在前面 对于循环中是0的进行判断祖先节点是否相等 相等就矛盾 打印no 直到循环结束flag还为1的话就打印yes
ac代码
#includebits/stdc.h
using namespace std;
//离散化步骤排序去重赋值
const int N300000;
int li[N],fa[N];
void first(int x){for(int i1;ix;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 t1find(a),t2find(b);fa[t1]t2;
}
struct node{int a,b,c;
}ne[100010];
bool cmp(node a,node b){return a.cb.c;
}
int main(){int n;cinn;while(n--){memset(fa,0,sizeof(fa));memset(li,0,sizeof(li));int t;cint;int cnt0;for(int i1;it;i){int x,y,z;cinxyz;ne[i]{x,y,z};li[cnt]x,li[cnt]y;//输入完成 开始离散}sort(li1,licnt1);//从1开始int lenunique(li1,li1cnt)-li-1;// coutlenendl;//len是用来 loow_bound里面的和初始化first的for(int i1;it;i){//离散赋值ne[i].alower_bound(li1,lilen1,ne[i].a)-li-1;ne[i].blower_bound(li1,lilen1,ne[i].b)-li-1;}// for(int i1;it;i){// //离散赋值// // ne[i].alower_bound(li1,licnt1,ne[i].a)-li-1;// // ne[i].blower_bound(li1,licnt1,ne[i].b)-li-1;// coutne[i].a ne[i].bendl;// }first(len);bool flag1;sort(ne1,ne1t,cmp);// for(int i1;it;i){// coutne[i].a ne[i].b ne[i].cendl;// }for(int i1;it;i){if(ne[i].c1){merge(ne[i].a,ne[i].b);}else if(ne[i].c0){if(find(ne[i].a)find(ne[i].b)){coutNOendl;flag0;break;}}}if(flag1) coutYESendl;}return 0;
}
