I. Invoking the Magic(并查集+unordered_map)

Problem - I - Codeforces

 题意:

包包是个懒惰的孩子。他有N双不同颜色的袜子，他每个月都要洗一次。在洗衣机里，这些袜子会被混在一起。

因为有太多的袜子需要配对，所以包包把整个袜子配对的过程分为两个阶段。

在第一阶段，BaoBao将袜子随机分配成对。然后在第二阶段，BaoBao重复以下操作，直到所有袜子配对完毕。包包选择一些成对的袜子，把它们放入他的魔法洗涤盆中，并使用他的魔法。如果他使用魔法时，魔法洗衣盆里的袜子能完美配对，魔法洗衣盆就会自动为包包配对。但是，如果他们不能（这意味着至少有一只袜子的颜色在盆子里是唯一的），魔法盆就会爆炸，包包不能让这种情况发生。

包包的魔法是有限的，在第一阶段之后，他需要知道他需要的魔法洗涤盆的最小容量，以成功配对所有的袜子。盆子的容量是指包包可以在同一时间内把最大数量的袜子放在魔法洗涤盆里。

输入
输入包含多个案例。输入的第一行包含一个正整数T（1≤T≤10），即案例的数量。

对于每个案例，输入的第一行包含一个整数n（1≤n≤105），即袜子的数量。

对于接下来的n行，第i（1≤i≤n）行包含两个整数ai和bi（1≤ai,bi≤230），表示第一阶段后第i对袜子的颜色。保证每只袜子都有一只相同颜色的袜子。

输出
对于每一种情况，打印一行包含一个整数，即魔法洗衣盆的最小容量。

input

1
5
1 2
2 3
1 3
4 5
4 5

output

题解:
利用并查集把所有在一个集合里的袜子指向同一个父节点,(注意要用unordered_map)

最后再把所有点找一遍父节点,看哪个父节点出现次数最多

#include
#include
#include
#include
using namespace std;
unordered_map<int,int> f;
int a[100050],b[100050];
int find(int x)
{
	if(f[x] == x)
	return x;
	return f[x] = find(f[x]);
}
void solve()
{
	int n;
	cin >> n;
	f.clear();
	unordered_map<int,int> vis;
	for(int i =1 ;i <= n;i++)
	{
		cin >> a[i];
		f[a[i]] = a[i];
		cin >> b[i];
		f[b[i]] = b[i];
	}
	for(int i = 1;i <= n;i++)
	{
		int x = find(a[i]);
		int y = find(b[i]);
		if(x!=y)
		{
			f[x] = y;
		}
	}
	int ma = 0;
	for(int i = 1;i <= n;i++)
	{
		vis[find(a[i])]++;
		vis[find(b[i])]++;
		ma = max(ma,vis[find(a[i])]);
		ma = max(ma,vis[find(b[i])]);
	}
	cout<2<<"\n";
	
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while(t--)
	{
		solve();
	}
}