UVa 10685 Nature

想法：

• Set[i]表示i這個node的father node(上面一層node的編號)，Root這個node的father node還是自己。
• Num[i]表示以i這個node為root的set，有幾個元素

這題與UVa 10608 Friends是一樣的，差別在於這題給的input為字串，因此我們先用map將它轉成數字編號。

	#include <iostream>
	#include <map>
	#include <string>
	using namespace std;
	map<string, int> Map;
	int Set[5010];
	int Num[5010];
	void Set_Initial(int N);
	int FindRoot(int x);
	void Union(int x, int y);
	int FindLargest(int N);
	int main()
	{
	ios::sync_with_stdio(false);
	int C, R;
	while (cin >> C >> R) {
	if (!C && !R) break;
	Set_Initial(C);
	string A, B;
	for (int i = 0; i < C; ++i) {
	cin >> A;
	Map[A] = i;
	}
	while (R--) {
	cin >> A >> B;
	Union(Map[A], Map[B]);
	}
	cout << FindLargest(C) << endl;
	}
	}
	void Set_Initial(int N)
	{
	Map.clear();
	for (int i = 0; i < N; ++i) {
	Set[i] = i;
	Num[i] = 1;
	}
	}
	int FindRoot(int x)
	{
	if (x == Set[x])
	return x;
	return Set[x] = FindRoot(Set[x]);
	}
	void Union(int x, int y)
	{
	x = FindRoot(x);
	y = FindRoot(y);
	if (x != y) {
	Set[x] = y;
	Num[y] += Num[x];
	}
	}
	int FindLargest(int N)
	{
	int Max = 0;
	for (int i = 0; i < N; ++i)
	if (Num[i] > Max) Max = Num[i];
	return Max;
	}

view raw [UVa] 10685 Nature.cpp hosted with ❤ by GitHub