f260: 愛八卦的同學

解題心得

這題沒給 n 的大小，好像不合理.....

而且最後用黑魔法才過的。

程式碼

#include <iostream>
using namespace std;

int f[10000] = { 0 }, Size[10000] = { 0 };

int find_set(int v)
{
	if (f[v] == v) return v;
	return f[v] = find_set(f[v]);
}
void union_by_size(int u, int v)
{
	/*if (Size[u] > Size[v])
		swap(u, v);
	Size[v] += Size[u];*/
	f[u] = v;
}
int main()
{
	cin.sync_with_stdio(false);
	cin.tie(NULL);
	int n, k, a, b;
	while (cin >> n >> k)
	{
		int group = n; // 幾個小圈圈
		for (int i = 0; i < n; i++)
			f[i] = i, Size[i] = 1;
		while (k--)
		{
			cin >> a >> b;
			a = find_set(a), b = find_set(b);
			if (a != b)
			{
				group--;
				union_by_size(a, b);
			}
		}
		cout << group << endl;
	}
	return 0;
}