1. 二分
小数
double l = 0,r = 100000,eps = 1e-4;
while (r-l >= eps){
double mid=(l+r)/2;
if (check(mid)) l=mid;
else r=mid;
}
整数
int l = 1,r = n,mid = (l+r)>>1;
while (l<r){
mid = (l+r+1)>>1;
if (check(mid)) l = mid;
else r = mid-1;
}
2. 并查集
int init(){
for (int i = 1;i <= n;i++) fa[i] = i;
}
int find(int x){
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void update(int x,int y){
int fu = find(x),fv = find(y);
fa[fu] = fv;
}