并查集

本次题目：简单题但卡壳了

题目简叙：将这个无向图建立起来，对其进行操作：删除最小边数，使其不再有环，求最小操作次数

想法：使用并查集，把相连的集合合并，然后再进行遍历，判断有几个find(i)==i，就是对应的环数，就这样吗？
不对，假如这个集合有多个环呢？所以，我们一开始就要算对于集合中多余的环数，怎么算？
假如一个集合只有一个环，那他的点数应该等于边数
所以我们先要除去多余的边数，然后再进行find(i)==i判断累加即可

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=200010;
int f[N];
int n, m, ans, cnt;
int find(int x)
{
	if(f[x]!=x) f[x]=find(f[x]);
	return f[x];
	
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	f[i]=i;
	for(int i=1;i<=m;i++)
	{
		int p, q;
		cin>>p>>q;
		f[find(p)]=find(q);
	}
	int cnt=m-n;
	for(int i=1;i<=n;i++)
	{
		if(find(i)==i)
		cnt++;
	}
	cout<<cnt<<endl;
	return 0;
}