本文主要是介绍sicily 1876. Basic Graph Problem 线段树+并查集+路径压缩，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
线段树或者RMQ都可以做，虽然是不是动态变化的，但是用线段树做也不错，，而且最近才开始弄线段树，当练练手。。。
一定要路径压缩的并查集，，不然线性的话，耗时过高。。。
而且不能写递归的路径压缩，我猜得。。。
因为n<=100000，一般20000就会栈爆的，，，，
#include<iostream>
#include<cstdio>#include<cstring>
using namespace std;
int n;
int w[100100];
struct node{
int left;
int right;
int min;
int max;
}seg[4*100000];
int father[100010];
void build(int p,int x,int y){
seg[p].left = x;
seg[p].right = y;
if(x==y){
// seg[p].left = seg[p].right = x;
seg[p].max = seg[p].min = w[x];
return ;
}
int mid = (x+y)/2;
build(2*p,x,mid);
build(2*p+1,mid+1,y);
int minl,minr,maxl,maxr;
minl = seg[2*p].min,maxl = seg[2*p].max;
minr = seg[2*p+1].min,maxr = seg[2*p+1].max;
if(minl<minr)seg[p].min = minl;
else seg[p].min = minr;
if(maxl>maxr)seg[p].max = maxl;
else seg[p].max = maxr;
}
void find(int p,int x,int y,int &min,int &max){
if(x==seg[p].left && y==seg[p].right){
min = seg[p].min;
max = seg[p].max;
return ;
}
int mid = (seg[p].left+seg[p].right)/2;
if(mid>=y){
find(2*p,x,y,min,max);
}else if(mid<x){
find(2*p+1,x,y,min,max);
}else {
int min1,min2,max1,max2;
find(2*p,x,mid,min1,max1);
find(2*p+1,mid+1,y,min2,max2);
min = min1<min2?min1:min2;
max = max1>max2?max1:max2;
return ;
}
}
int f(int a){///查找过程路径压缩
int i = a;
while(a!=father[a])a = father[a];
while(i!=a){
int tmp = father[i];
father[i] = a;
i = tmp;
}
return a;
}
void union_set(int u,int v){
int a = f(u);
int b = f(v);
if(a==b)return ;
if(a<b)father[b] = a;
else father[a] = b;
}
int main(){
int casenum = 0;
while(scanf("%d",&n)!=EOF){
if(casenum)printf("\n");
printf("CASE %d\n",++casenum);
for(int i = 1;i<=n;i++){
scanf("%d",&w[i]);
father[i] = i;
}
build(1,1,n);
int m;
scanf("%d",&m);
int u,v;
int min,max;
for(int i = 1;i<=m;i++){
scanf("%d%d",&u,&v);
find(1,u,v,min,max);
/// printf("%d %d\n",min,max);
union_set(min,max);
}
int k;
scanf("%d",&k);
for(int i = 0;i<k;i++){
scanf("%d%d",&u,&v);
if(f(u)==f(v))printf("YES\n");
else printf("NO\n");
}
}
return 0;
}
这篇关于sicily 1876. Basic Graph Problem 线段树+并查集+路径压缩的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
