No.7.2 并查集算法

暂时没看懂，只做记录，后续再究！

一、求有几个强盗同伙？

现在有10个强盗：

　　1与2是同伙；　　3与4是同伙；

　　5与2是同伙；　　4与6是同伙；

　　2与6是同伙；　　8与7是同伙；

　　9与7是同伙；　　1与6是同伙；

　　2与4是同伙；

　　强盗同伙的同伙，也是同伙。请问共有几个独立的强盗同伙？

解题思路：

　　1.首先假设10个强盗各不相属，用一维数组表示 f[i] = i

　　2.合并同伙：如果两人是同伙，以靠左原则为准，比如：“5与2是同伙，左边是5，那么2从属于5”  <=>

　　　　1). u,v ( f[u]=u, f[v]=v ), 靠左原则 f[v]=u;

　　　　2). w,v ( f[w]=w, f[v]=u ), "擒贼先擒王"原则，u,v 都要从属于 w, 即 f[v]=w; f[u]=w;

　　　　3). v, x ( f[v]=w, f[x]=x ), x 从属于 v，f[x] = f[v] = w;

　　上述过程即并查集算法：每个点开始都是只有一个节点的树，通过一些条件合并成一颗大树，合并过程要遵循靠左原则和擒贼先擒王原则，找到相同的父节点和根节点。

二、code

int t[100]={0},n,m;

//初始化，t[i]=i，表示每个点都是自己的父节点，相互之间没有关系
void init(){
　　int i;
　　for(i=1;i<=n;i++){
　　　　t[i]=i;
　　}
}

int getf(int v){　　// 寻找根节点
　　if(t[v] == v)
　　　　return v;
　　else{
　　　　t[v]=getf(t[v]);　　// v 是一维数组的索引坐标，t[v] 才是其父节点，所以 t[v] = getf( t[v] ); 在递归过程中，中间节点的父节点也被更新
　　　　return t[v];　　　  // 返回值是父节点，不是 v
　　}
}

/* 其实这个函数用一句就可以代替：t[ getf(y) ] = t[ getf(x) ];

void merge(int x,int y){

　　int t1,t2;
　　t1=getf(x);
　　t2=getf(y);
　　if(t1!=t2){
　　　　t[t2]=t1;
　　}
}

*/

int main(){
　　int i,a,b;
　　int num=0;
　　scanf("%d %d",&n,&m);
　　init();

　　for(i=1;i<=m;i++){
　　　　scanf("%d %d",&a,&b);
　　　　t[ getf(b) ] = t[ getf(a) ];
　　}

　　for(i=1;i<=n;i++)
　　　　printf("%d ",t[i]);

　　for(i=1;i<=n;i++){
　　　　if(t[i]==i)　　// 在假设的前提下，只有根节点的值不变，可以求出群的个数
　　　　　　num++;
　　}
　　printf("\n%d\n",num);
　　getchar();getchar();return 0;
}

三、代码不大，算法也不难，关键是怎么分解、实现。这是才是入门的基础！