题解：P16237 [蓝桥杯 2026 省 B] 应急布线

· · 题解

思路

这是一个标准的并查集题目，首先我们要对所有的边跑一遍并查集，然后将每个集合看作一个点，这时集合数减一就是连接的跳线数，然后平均单机最小跳线数就是将连接的跳线数乘上二再除以机数就行。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int fa[N];
int find(int x)//标准并查集
{
    if(fa[x]!=x)
    {
        fa[x]=find(fa[x]);
    }
    return fa[x];
}
void hebing(int x,int y)
{
    int u=find(x);
    int v=find(y);
    fa[u]=v;
}
int main()
{
    int n,m,x,y;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;//初始化
    }
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        hebing(x,y);//合并
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(fa[i]==i)
        {
            ans++;//统计跳线数
        }
    }
    cout<<ans-1<<" ";//可添加最少跳线数
    cout<<ceil(2.0*(ans-1)/n);//单机最大跳线数
    return 0;
}