带权的快速合并算法将执行至少顺着指针走lgN步
我想问这的lgN是如何得来的？
算法实现如下：
static const int N = 10000;
int main(){    
    int i, j,p,q,id[N],sz[N]; 
    for(i=0;i<N;i++){
     id[i]=i;sz[i]=1;}
    while(cin>>p>>q)
   {
    for (i=p; i!=id[i]; i=id[i]);    //寻找p所属集合的根 
        
    for (j=q; j!=id[j]; j=id[j])    //寻找q所属集合的根 
        ;
    
    if (i == j)    //已经连通 
        return true;
    
    if ( sz[i] > sz[j])    //合并p，q，即二者指向同一个根，并且总是将小的树连接到大的树上
    {
        id[j] = i;
        sz[i] += sz[j];
    }    
    else
    {
        id[i] = j;
        sz[j] += sz[i];
    }  
    cout<<" "<<p<<" "<<q<<endl;
   }     
}