首页 > 其他 > 详细

并查集模板 && 带权并查集模板

时间:2017-02-19 23:45:09      阅读:192      评论:0      收藏:0      [点我收藏+]

  不带权:

 1 int f[50050];
 2 void init(void)
 3 {
 4     for(int i=1;i<=n;i++)
 5         f[i]=i;
 6 }
 7 int fd(int x)
 8 {
 9     return f[x]==x?x:fd[x]=fd(f[x]);
10 }
11 int uion(int x,int y)
12 {
13     int fa=fd(x),fb=fd(y);
14     if(fa!=fb)f[fa]=fb;
15 }

  带权:

 1 int f[K],rl[K];
 2 
 3 void init(void)
 4 {
 5     for(int i=1;i<=n;i++)
 6         f[i]=i;
 7 }
 8 int fd(int x)
 9 {
10     if(f[x]==x) return x;
11     int fa=f[x];
12     f[x]=fd(f[x]);
13     rl[x]=(rl[x]+rl[fa])%2;
14     return f[x];
15 }
16 void join(int x,int y,int op)
17 {
18     int fx=fd(x),fy=fd(y);
19     if(fx==fy)return;
20     f[fy]=fx;
21     rl[fy]=(op+rl[x]+rl[y])%2;
22 }

 

并查集模板 && 带权并查集模板

原文:http://www.cnblogs.com/weeping/p/6417636.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!