之前有转过一篇：

这里按的实现写一遍。解一下下面这道题。

假如已知有n个人和m对好友关系（存于数字r）。如果两个人是直接或间接的好友（好友的好友的好友…），则认为他们属于同一个朋友圈，请写程序求出这n个人里一共有多少个朋友圈。

假如：n = 5 ， m = 3 ， r = {

{1 , 2} , {2 , 3} , {4 , 5}}，表示有5个人，1和2是好友，2和3是好友，4和5是好友，则1、2、3属于一个朋友圈，4、5属于另一个朋友圈，结果为2个朋友圈。

1 #include 
     
       2  3 int findFather(int* father, int n, int i) { 4     if (father[i] != i) { 5         father[i] = findFather(father, n, father[i]); //compress 6     } 7     return father[i]; 8 } 9 10 bool merge(int* father, int* rank, int n, int i, int j) {11     if (i < 0 || i >= n || j < 0 || j >= n) return false;12     int fi = findFather(father, n, i);13     int fj = findFather(father, n, j);14     if (fi == fj) return false;15     if (rank[fi] == rank[fj]) {16         father[fj] = fi;17         rank[fi]++;18     } else if (rank[fi] > rank[fj]) {19         father[fj] = fi;20     } else {21         father[fi] = fj;22     }23     return true;24 }25 26 int main(int argc, char** argv) {27     freopen("input.txt", "r", stdin);28     int n, m;29     scanf("%d%d", &n, &m);30     int* father = new int[n];31     int* rank = new int[n];32     for (int i = 0; i < n; ++i) {33         father[i] = i;34         rank[i] = 0;35     }36 37     int circles = 0;38     for (int k = 0; k < m; ++k) {39         int i, j;40         scanf("%d%d", &i, &j);41         circles += (merge(father, rank, n, i, j) ? 1 : 0);        42     }43     44     printf("circles: %d\n", circles);45     delete[] father, rank;46     return 0;47 }
     

并查集的复杂度：

每个操作的平均时间仅为$O(\alpha(n))$，$\alpha(n)$是$n = f(x) = A(x,x)$的反函数，并且A是急速增加的阿克曼函数。因为$\alpha(n)$是其的反函数，$\alpha(n)$对于可观的巨大n还是小于5。因此，平均运行时间是一个极小的常数。

kruscal算法