专栏文章

题解：AT_abc399_c [ABC399C] Make it Forest

__qumingnan_
AT_abc399_c题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miprsb1m
此快照首次捕获于
2025/12/03 16:53
3 个月前
此快照最后确认于
2025/12/03 16:53
3 个月前
查看原文
题目跳楼机

正文开始

阅读理解

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

思路：

先看定义，森林，一个无环图。我们可以把他看成一个由 nn 棵树组成的图。
我们知道，一颗有 nn 个点的树是有 n−1n-1 条边的，也就是说，这个森林中每一个连通块都应该是有 xx 个点 x−1x-1 条边，另连通块个数为 ss，也就是说这个森林应该有 n−sn-s 条边。
那既然应该有 n−sn-s 条边，那题目中给出了 mm 条边，就用 m−(n−s)m-(n-s) 即可得到最终答案（注意结果要大于等于 00）。

代码

CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...