[SGU174 Walls]并差集、排序+二分查找

【题目大意】
给出一些只在端点相交的线段。
问在连了第几条边之后，这些线段中的一部分连成了一个完整的封闭图形。
【算法分析】
封闭图形就是一个环，如果已经成同一连通分量的两个点再被连，就是成环了。
这个可以用并差集判断。
然后我们需要快速查找点。
由于本题都是静态的东西，所以快排+二分足矣。
如果需要动态算法可以考虑hash表和平衡树。
【其它】1A
【CODE】

#include #include #include struct Point{int x,y;}list[400005],a[200005][2];
int n,tot,f[400005];

void input(){
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%d%d%d%d",&a[i][0].x,&a[i][0].y,&a[i][1].x,&a[i][1].y);
list[++tot]=a[i][0];
list[++tot]=a[i][1];
}
}

int Findst(int x){
int l=1,r=tot,mid;
while (l mid=(l+r)/2;
if (x>list[mid].x) l=mid+1;
else r=mid;
}
return l;
}

int Finded(int x){
int l=1,r=tot,mid;
while (l+1 mid=(l+r)/2;
if (x>=list[mid].x) l=mid;
else r=mid-1;
}
if (x==list[r].x) return r;
return l;
}

int Find(Point tmp){
int l=Findst(tmp.x),r=Finded(tmp.x),mid;
while (l mid=(l+r)/2;
if (tmp.y>list[mid].y) l=mid+1;
else r=mid;
}
return l;
}

int cmp(const void *x,const void *y){
if (((Point*)x)->x==((Point*)y)->x) return ((Point*)x)->y-((Point*)y)->y;
return ((Point*)x)->x-((Point*)y)->x;
}

int GF(int p){
if (f[p]==p) return p;
return f[p]=GF(f[p]);
}

void solve(){
for (int i=1;i<=tot;i++) f[i]=i;
for (int x,y,i=1;i<=n;i++){
x=Find(a[i][0]);
y=Find(a[i][1]);
if (GF(x)==GF(y)){
printf("%dn",i);
return;
}
f[f[x]]=f[y];
}
printf("0n");
}

int main(){
input();
qsort(list+1,tot,sizeof(Point),cmp);
solve();
}