题解：AT_abc399_c [ABC399C] Make it Forest

· · 题解

题目跳楼机

正文开始

阅读理解

有一个无向图（无自环），求删几条边可以变成森林。

思路：

先看定义，森林，一个无环图。我们可以把他看成一个由 n 棵树组成的图。

我们知道，一颗有 n 个点的树是有 n-1 条边的，也就是说，这个森林中每一个连通块都应该是有 x 个点 x-1 条边，另连通块个数为 s，也就是说这个森林应该有 n-s 条边。

那既然应该有 n-s 条边，那题目中给出了 m 条边，就用 m-(n-s) 即可得到最终答案（注意结果要大于等于 0）。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int b[300005],f[300005],s;
int ans;
int fine(int x){//并查集求连通块 
    if(f[x]==x)return x;
    return f[x]=fine(f[x]);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)//初始化 
        f[i]=i;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        f[fine(x)]=f[fine(y)];
    }
    for(int i=1;i<=n;i++){//统计连通块个数 
        b[f[fine(i)]]++;
        if(b[f[fine(i)]]==1)s++;
    }
    cout<<max(0ll,m-n+s);
    return 0;
}