Set - Disjoint Set: Union Find Tree
#include<stdio.h>
#include<map>
int parents[10001];
int parentSearch(int p){
return (parents[p]=(p==parents[p]?p:parentSearch(parents[p])));
}
void parentUpdate(int p,int top){
if(p!=parents[p]){
parentUpdate(parents[p],top);
}
parents[p]=top;
}
void numUnion(int x,int y){
int topX=parentSearch(x);
int topY=parentSearch(y);
parentUpdate(topX,topY);
}
bool isSame(int x,int y){
return parentSearch(x)==parentSearch(y);
}
int main(){
int n,q,com,x,y;
scanf("%d %d",&n,&q);
for(int i=0;i<=n;i++){
parents[i]=i;
}
for(int i=0;i<q;i++){
scanf("%d %d %d",&com,&x,&y);
if(com==0){
numUnion(x,y);
}else{
printf("%s\n",isSame(x,y)?"1":"0");
}
}
}
Range Query - Range Minimum Query
#include<stdio.h>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <list>
#include <set>
const int MAX=100001;
const int INITIAL_VALUE=2147483647;
struct myFind{
int s,t,num,no;
};
struct myUpdate{
int x,y,no;
bool operator<(const myUpdate& up)const{
if(y!=up.y)return y<up.y;
return no<up.no;
}
};
int main(){
int n,q,com,x,y;
std::map<int,std::list<myFind> > fs;
std::map<int,std::set<int> > stops;
std::vector<myUpdate> ups;
std::vector<myFind> ans;
myFind f1;
myUpdate u1;
scanf("%d %d",&n,&q);
int no=0,no1=0;
for(int i=0;i<q;i++){
scanf("%d %d %d",&com,&x,&y);
if(com==0){
no++;
u1.no=no;
u1.x=x;
u1.y=y;
ups.push_back(u1);
stops[x].insert(no);
}else{
f1.s=x;
f1.t=y;
f1.no=no1;
f1.num=INITIAL_VALUE;
fs[no].push_back(f1);
ans.push_back(f1);
no1++;
}
}
no++;
std::sort(ups.begin(),ups.end());
for(int i=0;i<ups.size();i++){
u1=ups[i];
std::map<int,std::list<myFind> >::iterator it;
std::list<myFind>::iterator lIt;
std::set<int>::iterator sIt;
sIt=stops[u1.x].upper_bound(u1.no);
int stopNo;
if(sIt==stops[u1.x].end())stopNo=no;
else stopNo=(*sIt);
for(it=fs.lower_bound(u1.no);it!=fs.end();it++){
int nowNo=(*it).first;
if(stopNo<=nowNo)break;
for(lIt=(*it).second.begin();lIt!=(*it).second.end();){
f1=(*lIt);
if(f1.s<=u1.x && u1.x<=f1.t){
ans[f1.no].num=u1.y;
lIt=(*it).second.erase(lIt);
}else{
lIt++;
}
}
}
}
for(int i=0;i<ans.size();i++){
printf("%d\n",ans[i].num);
}
}
最終更新:2014年01月24日 08:22