并查集和带权并查集

一、并查集：

并查集是若干个不相交集合，能够实现较快的合并和判断元素所在集合的操作。

主要组成部分及操作：

1，初始化：初始化后，每一个元素的父亲节点是他本身，每一个元素的祖先节点也是他本身

 C++ Code  1 2 3 4 5 6 7 void makeSet( int n) {      for ( int i =  0; i < n; i++)     {         par[i] = i;     } }

2，查找：查找一格元素所在的集合，也就是找到这个元素所在集合的祖先。(通常在查找的过程中加入路径压缩)

递归写法：

 C++ Code  1 2 3 4 5 6 7 8 9 10 /* 查找x元素所在的集合,回溯时压缩路径*/ int Find_Set( int x) {      if (x != father[x])     {         father[x] = Find_Set(father[x]);  //这个回溯时的压缩路径是精华    }      return father[x]; } 非递归写法：

 C++ Code  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 int Find( int x)   ///查找根节点{      int r = x;      while(r != pre[r])   ///返回路径r        r = pre[r];      int i = x, temp;      while(pre[i] != r)   ///压缩路径    {         temp = pre[i];  ///在改变上级之前用临时变量  j 记录下他的值        pre[i] = r;    ///把上级改为根节点        i = temp;     }      return r; } ps:建议用递归写法，代码简洁。

3，合并操作：合并两个不相交集合的操作，先利用查找操作找到两个集合的祖先，将一个集合的祖先指向另一个集合的祖先

 C++ Code  1 2 3 4 5 6 7 8 9 10 11 void Union( int r1,  int r2) {      ///并     int t1 = fin_d(r1);      int t2 = fin_d(r2);      if(t1 != t2)     {         a[t2] = t1;          ///合并子节点    } }

总的来说，并查集由一个数组，一个查找操作以及一个合并操作组成，

有的题目在合并的时候 需要根据  秩 合并，并实时更新 秩 ，只不过是多加了一个数组存储 秩。

二、带权并查集

1，概述

        带权并查集就是节点存有权值的并查集，多维护一个数组来维护权值，这个权值通常表示当前点与根节点之间的关系。

2，代码实现

 Java Code  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 #include<bits/stdc++.h> using namespace std; const   int  INF =  100000  +  4 ; int  dis[INF]; int  n, m, q; int  fa[INF]; ///初始化， void  init(){     for ( int  i =  1 ; i <= n; i++)    {        dis[i] =  0 ;        fa[i] = i;    }} ///查，同时进行路径压缩以及权值数组的维护 int   Find( int   x){     if (fa[x] == x)    {         return  x;    }     int  t = fa[x];    fa[x] = Find(fa[x]);   ///路径压缩     dis[x] += dis[t];     ///更新与根的关系      return  fa[x];} ///并，注意权值数组的操作 void  Union( int   x,  int   y,  int   tx,  int  ty,  int   d){    fa[ty] = tx;    dis[ty] = dis[x] + d - dis[y];} int  main(){     while (~scanf( "%d%d%d" , &n, &m, &q))    {        init();         for ( int  i =  1 , x, y, z; i <= m; i++)        {             ///点x，y，以及他们之间的距离             scanf( "%d%d%d" , &x, &y, &z);             int   tx = Find(x);             int   ty = Find(y);             if (tx != ty)                Union(x, y, tx, ty, z);        }         for ( int  i =  0 , x, y; i < q; i++)        {            scanf( "%d%d" , &x, &y);             if (Find(x) == Find(y))                printf( "%d\n" , dis[y] - dis[x]);             else             {                printf( "-1\n" );            }        }    }     return   0 ;}