并查集（Union-Find）
Date：2019-06-23 13:42:53
1 //定义2 int father[N]; //father[1]=2,即2是1的父亲，根结点用father[i]=i表示34 //初始化5 for(int i=1; i<=N; i++)6 father[i]=i; //初始时有N个独立的集合78 //查找9 //对于给定的结点，寻找其根结点10 int Find(int x)11 {12 if(father[x] == x)13 return x;14 Find(father[x]);15 }1617 //合并18 void Union(int a, int b)19 {20 int fa = Find(a);21 int fb = Find(b);22 father[fb] = fa; //不能用father[a]=b23 Find2(b); //将fb中的结点更新至fa24 }252627 //路径压缩28 //把当前查询结点的路径上所有的结点的父亲都指向根结点29 int Find2(int x)30 {31 int r = x;32 while(x != father[x])33 x = father[x];34 //此处x已经是根结点35 while(r != father[r])36 {37 int z = r;38 r = father[r];39 father[z] = x;40 }41 }4243 //递归写法44 int Find2(int x)45 {46 if(x == father[x])47 return x;48 fathre[x] = Find2(father[x]);49 }
转载于
//www.cnblogs.com/blue-lin/p/11072511.html
古城微笑少年丶
港控/mmm°
Myth丶恋晨
左手的ㄟ右手
还没有评论，来说两句吧...