题解 | #加边的无向图#

【路径压缩】【按秩合并】

• 题目考点：并查集

• 题目大意：求连通块个数

• 题目分析：正常并查集代码，从前往后扫，遇到不在同一个连通块时ans++；题目数据无需优化，代码里贴上路径压缩+按秩合并代码，有兴趣的同学可以大概看看；

• 代码：

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 100010;
int n, m, f[N];

int find(int x)
{
    return f[x] == x ? f[x] : f[x] = find(f[x]);
    /*
    ***************** 路径压缩：*****************
    while(x != f[x])
    {
        f[x] = f[f[x]];
        x = f[x];
    }
    return x;
    */
}

void merge(int a, int b)
{
    f[find(a)] = find(b);
    return ;

    /*
    ***************** 按秩合并 *****************（需要rank数组,n个元素初始化为1）
    int fa = find(a), fb = find(b);
    if(fa == fb) return ;
    if(rank[fa] > rank[fb])f[fa] = fb;
    else if(rank[fa] < rank[fb]) f[fb] = fa;
    else 
        f[fa] = fb, rank[fb] ++;
    return ;
    */
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)f[i] = i;
    while(m--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        merge(a, b);
    }
    int ans = 0;
    int f1 = find(1);
    for(int i = 2; i <= n; i++)
    {
        if(find(i) != f1)
        {
            ans ++;
            merge(i, 1);
        }
    }
    printf("%d", ans);
    return 0;
}