PAT L2-024. 部落
原题链接
简单
作者:
青丝蛊
,
2021-04-13 17:03:56
,
所有人可见
,
阅读 257
#include <bits/stdc++.h>
using namespace std;
int p[10010];
int ans; //统计合并多少次,最后总人数减合并多少次就是部落个数
int find(int x)
{
return x == p[x] ? x : p[x] = find(p[x]);
}
void unite(int x, int y)
{
x = find(x), y = find(y);
if (x != y) p[y] = x, ans--;
}
int main()
{
int n;
cin >> n;
iota(p, p + 10010, 0);
set<int> se;
while (n--)
{
int k; cin >> k;
int x, y; cin >> x;
se.insert(x);
for (int i = 1; i < k; i++) cin >> y, unite(x, y), se.insert(y);
}
cout << se.size() << ' ' << se.size() + ans << endl;
cin >> n;
while (n--)
{
int x, y; cin >> x >> y;
if (find(x) == find(y)) puts("Y");
else puts("N");
}
return 0;
}