欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

A1118 Birds in Forest [并查集]

程序员文章站 2022-06-11 14:29:28
...

A1118 Birds in Forest [并查集]

#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 10002;
int father[maxn], cnt[maxn];
int getfather(int x)
{
	int a = x;
	while (x != father[x])
		x = father[x];
	while (a != father[a])
	{
		int z = a;
		a = father[a];
		father[z] = x;
	}
	return x;
}
void Union(int a, int b)
{
	int fa = getfather(a);
	int fb = getfather(b);
	if (fa != fb)
		father[fa] = fb;
}
bool exist[maxn];
int main()
{
	int n, k, temp1, temp2, queryn, treenum = 0, birdsnum = 0;
	cin >> n;
	for (int i = 0; i < maxn; i++)
		father[i] = i;
	for (int i = 0; i < n; i++)
	{
		cin >> k >> temp1;
		exist[temp1] = true;
		for (int j = 0; j < k - 1; j++)
		{
			cin >> temp2;
			exist[temp2] = true;
			Union(temp1, temp2);
		}
	}
	for (int i = 0; i < maxn; i++)
	{
		if (exist[i])
			cnt[getfather(i)]++;
	}
	for (int i = 0; i < maxn; i++)
	{
		if (cnt[i] != 0)
		{
			treenum++;
			birdsnum += cnt[i];
		}
	}
	cout << treenum << " " << birdsnum << endl;
	cin >> queryn;

	for (int i = 0; i < queryn; i++)
	{
		cin >> temp1 >> temp2;
		if (getfather(temp1) == getfather(temp2))
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}
}