并查集,以及可拆分并查集-白红宇

并查集,以及可拆分并查集

阅读量：4655 次

发布时间：2019-06-09

本文共 9108 字，大约阅读时间需要 30 分钟。

普通并查集. 合并均摊O(log(n)) 查询均摊O(log(n))

1 //常用版本 2  3 //Union Find 4 int f[1005000]; 5  6 void INIT(int size) 7 { for(int i=0;i<=size;i++) f[i]=i; } 8  9 int findf(int x) 10 { return f[x]==x ? x : f[x]=findf(f[x]); };11 12 int connect(int x)13 { f[findf(a)]=findf(b); }

VIJOS 1443 会卡掉不加启发式的并查集.

优化并查集. 加上了启发式合并. 复杂度: 合并均摊O(α(n)); 查询均摊O(α(n)). α函数是Ackerman函数的反函数.一般认为其小于等于4.

1 //union find 2 int f[5000],r[5000]; 3 inline void INIT(int size) 4 { for(int i=0;i
     
      r[b]) swap(a,b);12     int fa=findf(a);13     int fb=findf(b);14     r[fb]+=r[fa];15     f[fa]=fb;16 }

使用r数组表示"秩",即集合大小,存储在每个集合的根节点.

合并的时候将秩小的集合的根节点的父亲设到秩大的集合的根.

常数较上者而言更加大.

另外,如果离线处理询问,那么可以通过建图然后FloodFill的方式达到严格O(n)预处理+O(1)询问,常数较大.

可拆分并查集.

最坏情况: 合并 O(n) 查询 O(n) 拆分 O(n)

平均情况(对于随机生成的数据): 合并 O(logn) 查询 O(logn) 拆分 O(logn)

对于某种方式生成的随机数据跑得很快的样子?

反正随便卡.....

1 //union find 2 int f[1050]; 3 void INIT(int size) 4 { for(int i=0;i<=size;i++) f[i]=i; } 5  6 int findf(int x) 7 { while(f[x]!=x) x=f[x]; return x; } 8  9 void setroot(int x)10 { if(f[x]!=x) setroot(f[x]); f[x]=f[f[x]]=x; }11 12 void link(int a,int b)13 { setroot(a); f[a]=b; }14 15 void cut(int a,int b)16 { setroot(a); f[b]=b; }

可以看到后边这种比较像LCT...

链式并查集.

复杂度均摊 O(nlogn)

AC VIJOS 1443 银河英雄传说

常数好大....复杂度也好大.......这道题用了1653ms.....

这个并查可以用于维护一些奇怪的东西..... (做这题的时候脑子里全是LCT怎么办)

1 //Union Find 2 int L[30050]; //left node pointer. 3 int R[30050]; //right node pointer. 4 int C[30050]; //center node. 5 int tot[30050]; //chain nodes amount. 6 int nxt[30050]; //next node. 7 int v[30050]; //value of all nodes. 8  9 void INIT(int size)10 {11     for(int i=0;i<=size;i++)12     L[i]=R[i]=C[i]=i,tot[i]=1,nxt[i]=-1;13 }14 15 void Merge(int x,int y)16 {17     //link x to y's tail.18     int cx=C[x];19     int cy=C[y];20     if(tot[cx]>tot[cy]) //change chain y's info21     {22         for(int i=L[cy];i!=-1;i=nxt[i])23             C[i]=cx; //chagne center node.24         nxt[R[cy]]=L[cx];25         L[cx]=L[cy];26         tot[cx]+=tot[cy];27     }28     else //change chain x's info.29     {30         for(int i=L[cx];i!=-1;i=nxt[i])31             C[i]=cy; //change center node.32         nxt[R[cy]]=L[cx];33         R[cy]=R[cx];34         tot[cy]+=tot[cx];35     }36 }37 38 39 char op[505000];40 int a[505000];41 int b[505000];42 43 int n=30000,m;44 45 int main()46 {47     m=getint();48     49     INIT(n);50     51     for(int i=0;i

View Code

做法就是对每一条链维护一个"中心节点",这个节点存储了链的总结点数,链的左端点和链的右端点.

合并的时候把这些存储的值的转移安排好就行了.......

实在不懂就看代码......

千万注意Merge函数中nxt数组赋值的顺序......

next数组的值一定要在cx赋值完毕以后修改,不然赋值操作会把一整个集合扫一遍!....

这样总时间复杂度就是O(n^2)的了....害我T了一发 TAT

AC BZOJ 1483 又是按秩合并.....

全都是调试用的注释的版本

1 #include 
      
         2 #include 
       
          3 #include 
        
           4    5 #include 
         
            6 #include 
          
             7 #include 
           
             8 #include 
            
              9 10 #include 
             
               11 #include 
              
                12 #include 
                13 #include 
                
                  14 #include 
                 
                   15 #include 
                  
                    16 17 typedef unsigned int uint; 18 typedef long long int ll; 19 typedef unsigned long long int ull; 20 typedef double db; 21 typedef long double ldb; 22 23 using namespace std; 24 25 inline int getint() 26 { 27 int res=0; 28 char c=getchar(); 29 bool mi=false; 30 while((c<'0' || c>'9')/* && !feof(stdin)*/) mi=(c=='-'),c=getchar(); 31 while('0'<=c && c<='9'/* && !feof(stdin)*/) res=res*10+c-'0',c=getchar(); 32 return mi ? -res : res; 33 } 34 inline ll getll() 35 { 36 ll res=0; 37 char c=getchar(); 38 bool mi=false; 39 while(c<'0' || c>'9') mi=(c=='-'),c=getchar(); 40 while('0'<=c && c<='9') res=res*10+c-'0',c=getchar(); 41 return mi ? -res : res; 42 } 43 44 //============================================================================== 45 //============================================================================== 46 //============================================================================== 47 //============================================================================== 48 49 50 int C[105000]; //color array. 51 int N[1005000]; //store the amount of same-color node. 52 int F[105000]; //father(center) node of this color 53 int L[105000]; //what color do this node actually have. 54 int R[105000]; //root of a chain. 55 56 int p[1005000]; //pointer to the previous same-color node. 57 int t[1005000]; //true color of "color code". 58 59 int n,m; 60 int res; 61 62 void ChangeColor(int i,int color) 63 { 64 if(C[i-1]!=C[i] && C[i-1]==color) res--; 65 if(C[i+1]!=C[i] && C[i+1]==color) res--; 66 if(C[i-1]==C[i] && C[i-1]!=color) res++; 67 if(C[i+1]==C[i] && C[i+1]!=color) res++; 68 C[i]=color; 69 } 70 71 72 int main() 73 { 74 freopen("in.txt","r",stdin); 75 freopen("out.txt","w",stdout); 76 77 n=getint(); 78 m=getint(); 79 C[0]=C[n+1]=-1; 80 for(int i=1;i<=n;i++) N[C[i]=getint()]++; 81 for(int i=1;i<=n;i++) res+=( C[i]!=C[i-1] ); 82 for(int i=1;i<=n;i++) { F[i]=p[C[i]]; p[C[i]]=i; } 83 for(int i=1;i<=n;i++) R[i]=( F[i] ? R[F[i]]:i ); 84 85 for(int i=0;i<=1000000;i++) t[i]=i; 86 87 //for(int i=1;i<=n;i++) 88 //printf("i:%d color:%d f:%d cnt:%d root:%d l:%d\n",i,C[i],F[i],N[i],R[i],L[i]); 89 90 91 //printf("p:");for(int i=1;i<9;i++) printf("%d ",p[i]); printf("\n"); 92 //printf("t:");for(int i=1;i<9;i++) printf("%d ",t[i]); printf("\n"); 93 //printf("C:");for(int j=1;j<=n;j++) printf("%d ",C[j]); printf("\n"); 94 95 for(int i=0;i
                   
                    N[t[b]]) swap(t[a],t[b]);105 //printf("change color %d[%d] to %d[%d]\n",t[a],R[p[t[a]]],t[b],R[p[t[b]]]);106 a=t[a]; b=t[b];107 108 int x=p[a],y=p[b]; if(!p[a]) goto FINAL; //continue;109 printf("%d %d\n",x,y);110 N[b]+=N[a]; N[a]=0; p[a]=0; p[b]=x;111 while(F[x]){ R[x]=R[y]; ChangeColor(x,b); x=F[x]; }112 R[x]=R[y]; ChangeColor(x,b); F[x]=y;113 }114 else if(c==2) printf("%d\n",res);115 116 /*117 FINAL: if(c!=2) {118 for(int i=1;i<=n;i++) if(p[t[i]]){ printf("color:%d .",t[i]); 119 for(int j=p[t[i]];j;j=F[j])printf("->%d",j); printf("\n");}120 printf("p:");for(int i=1;i<=n;i++) printf("%d ",p[i]); printf("\n");121 printf("t:");for(int i=1;i<=n;i++) printf("%d ",t[i]); printf("\n");122 printf("C:");for(int j=1;j<=n;j++) printf("%d ",C[j]); printf("\n"); }123 */124 }125 126 127 return 0;128 }129 130 131 /*132 10 2133 1 2 1 3 3 1 1 2 2 1134 1 2135 2 3136 */

View Code

不带注释的版本

1 #include 
      
         2 #include 
       
          3 #include 
        
           4    5 #include 
         
            6 #include 
          
             7 #include 
           
             8 #include 
            
              9 10 #include 
             
               11 #include 
              
                12 #include 
                13 #include 
                
                  14 #include 
                 
                   15 #include 
                  
                    16 17 typedef unsigned int uint; 18 typedef long long int ll; 19 typedef unsigned long long int ull; 20 typedef double db; 21 typedef long double ldb; 22 23 using namespace std; 24 25 inline int getint() 26 { 27 int res=0; 28 char c=getchar(); 29 bool mi=false; 30 while((c<'0' || c>'9')/* && !feof(stdin)*/) mi=(c=='-'),c=getchar(); 31 while('0'<=c && c<='9'/* && !feof(stdin)*/) res=res*10+c-'0',c=getchar(); 32 return mi ? -res : res; 33 } 34 inline ll getll() 35 { 36 ll res=0; 37 char c=getchar(); 38 bool mi=false; 39 while(c<'0' || c>'9') mi=(c=='-'),c=getchar(); 40 while('0'<=c && c<='9') res=res*10+c-'0',c=getchar(); 41 return mi ? -res : res; 42 } 43 44 //============================================================================== 45 //============================================================================== 46 //============================================================================== 47 //============================================================================== 48 49 50 int C[105000]; //color array. 51 int N[1005000]; //store the amount of same-color node. 52 int F[105000]; //father(center) node of this color 53 int L[105000]; //what color do this node actually have. 54 int R[105000]; //root of a chain. 55 56 int p[1005000]; //pointer to the previous same-color node. 57 int t[1005000]; //true color of "color code". 58 59 int n,m; 60 int res; 61 62 void ChangeColor(int i,int color) 63 { 64 if(C[i-1]!=C[i] && C[i-1]==color) res--; 65 if(C[i+1]!=C[i] && C[i+1]==color) res--; 66 if(C[i-1]==C[i] && C[i-1]!=color) res++; 67 if(C[i+1]==C[i] && C[i+1]!=color) res++; 68 C[i]=color; 69 } 70 71 72 int main() 73 { 74 n=getint(); 75 m=getint(); 76 C[0]=C[n+1]=-1; 77 for(int i=1;i<=n;i++) N[C[i]=getint()]++; 78 for(int i=1;i<=n;i++) res+=( C[i]!=C[i-1] ); 79 for(int i=1;i<=n;i++) { F[i]=p[C[i]]; p[C[i]]=i; } 80 for(int i=1;i<=n;i++) R[i]=( F[i] ? R[F[i]]:i ); 81 82 for(int i=0;i<=1000000;i++) t[i]=i; 83 84 for(int i=0;i
                   
                    N[t[b]]) swap(t[a],t[b]); 93 a=t[a]; b=t[b]; 94 95 int x=p[a],y=p[b]; if(!p[a]) continue; 96 N[b]+=N[a]; N[a]=0; p[a]=0; p[b]=x; 97 while(F[x]){ R[x]=R[y]; ChangeColor(x,b); x=F[x]; } 98 R[x]=R[y]; ChangeColor(x,b); F[x]=y; 99 }100 else if(c==2) printf("%d\n",res);101 102 }103 104 return 0;105 }