HDU 1213

最近家庭聚会也真不少，为啥做题这么应景...

水题，加上集合的利用，并查集

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
using namespace std;

const int maxn= 1e3;

int pa[maxn];
int T, N, M;
set<int> grp;

int Find(int x)
{
	if (x== pa[x]){
		return x;
	}

	return pa[x]= Find(pa[x]);
}
void Merge(int x, int y)
{
	x= Find(x);
	y= Find(y);

	if (x== y){
		return;
	}

	pa[y]= x;
}
void Init(int n)
{
	grp.clear();
	for (int i= 1; i< n+1; ++i){
		pa[i]= i;
	}
}

int main()
{
	int x, y;
	scanf("%d", &T);

	for (int i= 0; i< T; ++i){
		scanf("%d %d", &N, &M);
		Init(N);
		for (int j= 0; j< M; ++j){
			scanf("%d %d", &x, &y);
			Merge(x, y);
		}
		for (int j= 1; j< N+1; ++j){
			grp.insert(Find(j));
		}
		printf("%d
", int(grp.size()));
	}
	return 0;
}