并查集
看的很好的博文
链接如下
https://blog.csdn.net/chen134225/article/details/82052537
两个函数

1.查找

int pre[1000];
int find(int x)//查找x的顶级
{
    int r = x;
    while (pre[r] != r)//当r的上级是他自己，那么r就是顶级
    {
        r = pre[r];
        return r;
    }
}

2.合并

void join（int x,int y）
{
    int fx = find(x),fy = find(y);//找到两人的顶级
    if(fx != fy)
    pre[fx] = fy;// 如果两人的顶级不相等，那么一个人做上级，一个人做下级
}

相当于计算连通分支
如果1 和 2相连 2和3相连那么1 2 3相连

相当是划分集合的样子 都变为了树结构 应该后面还会有优化 等做到题再说吧

练习 hdu1232

链接如下
http://acm.hdu.edu.cn/showproblem.php?pid=1232
解题思路-并查集
先进行查找-合并 把相连通的连接到一起，计算有多少个连通分支，连通分支-1 即所需要的连接数。
代码如下

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
int pre[1005];
void Init(int n) {
    for(int i = 1; i<= n; i++) {
        pre[i] = i;
    }
}
int find(int x) {
    while(pre[x] != x) {
        x = pre[x];
    }
    return x;

}
void join(int a,int b) {
    int temp_a  = find(a),temp_b = find(b);
    if(temp_a != temp_b) {
        pre[temp_a] = temp_b;
    }
}
//确定连通分量
int find_ans(int n) {
    int sum = 0;
    for(int i = 1; i <=n; i++) {
        if(pre[i] == i)
            sum++;
    }
    return sum;
}
int main() {
    int n,m,a,b;
    while(scanf("%d",&n)!=EOF) {
        if(!n) break;
        Init(n);
        scanf("%d",&m);
        for(int i = 0; i < m; i++) {
            cin>>a>>b;
            join(a,b);
        }
        cout<<find_ans(n)-1<<'\n';
    }
    return 0;
}