a445: 新手訓練系列- 我的朋友很少

解題心得

disjoint set 練習。

完成 union(a,b), find_set(v), same_set(u, v) 就差不多能過了，只是 find_set 可以再進一步優化。

程式碼

#include <iostream>
using namespace std;

int n, m, q, f[10001] = { 0 };

void Union(int a, int b)
{
	f[a] = b;
}
int find_set(int v)
{
	while (f[v] != v)
		v = f[v];
	return f[v];
}
bool same_set(int a, int b)
{
	return find_set(a) == find_set(b);
}
int main()
{
	int a, b;
	cin >> n >> m >> q;

	for (int i = 1; i <= n; i++)
		f[i] = i;
	while (m--)
	{
		cin >> a >> b;
		Union(find_set(a), find_set(b));
	}
	while (q--)
	{
		cin >> a >> b;
		if (same_set(a, b))
			cout << ":)" << endl;
		else
			cout << ":(" << endl;
	}
	return 0;
}