并查集

代码

#include 
using namespace std; 
int num[100]; 
int getf(int v) // 查找v的根元素 
{
	if(num[v] == v) // 如果自己是直接的根元素 
		return v;
	else
	{
		num[v] = getf(num[v]); // 用递归找到根元素 
		return num[v];
	}
}
void add(int v, int u) // 合并函数 
{
	int t1, t2;
	t1 = getf(v); // 找到v的根元素 
	t2 = getf(u); // 找到u的根元素 
	if(t1 != t2) // 如果v的根元素不等于u的根元素则置为相同 
		num[t2] = t1;
}
int main()
{
	int a, b;
	int n, m, cnt = 0;
	cin >> a >> b;
	for(int i = 1; i <= a; i++) // 将每个人的根元素置为自己 
		num[i] = i;
	for(int i = 1; i <= b; i++) // 执行b次合并指令 
	{
		cin >> n >> m;
		add(n, m);
	}
	for(int i = 1; i <= a; i++)
		if(num[i] == i) // 如果自己的根元素为自己则为一个集合 
			cnt++;
	cout << cnt << endl;
}

输入:

10 9
1 2
3 4
5 2
4 6
2 6
8 7
9 7
1 6
2 4

输出:

3