一些科学家为森林中成千上万的鸟类拍照。
假设所有出现在同一张照片中的鸟都属于同一棵树。
请你帮助科学家计算森林中树木的最大数量,对于任何一对鸟类,请判断它们是否在同一棵树上。
输入格式
第一行包含整数 N 表示照片数量。
接下来 N 行,每行描述一张照片,格式如下:
K B1 B2 … BKK 表示照片中的鸟的数量,Bi 是鸟的具体编号。
保证所有照片中的鸟被连续编号为 1 到某个不超过 104 的整数。
再一行包含整数 Q。
接下来 Q 行,每行包含两个鸟的编号,表示一组询问。
输出格式
第一行输出最大可能的树的数量以及鸟的数量。
接下来对于每个询问,如果被询问的两个鸟在同一棵树,则在一行中输出 Yes,否则输出 No。
数据范围
1≤N≤104,1≤K≤10,1≤Q≤104
输入样例:
4
3 10 1 2
2 3 4
4 1 5 7 8
3 9 6 4
2
10 5
3 7
输出样例:
2 10
Yes
No
//树的个数就是根节点的数量
//鸟的个数就是所有节点的数量
//是否有关就判断find(x) == find(y);
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 10100;
int n,k,q;
int p[N];//记录父亲节点
int a[N];
int cnt[N];
bool st[N];
int find(int x)
{
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
int main()
{
cin >> n;
for(int i = 0; i < N; i ++) p[i] = i,cnt[i] = 1;//初始化
int maxx = -1;//因为编号是1~n 所以鸟的数量应该是最大的数字
//(如果不是这样的规律,也可以通过建造一个节点数量数组来记录)
for(int i = 0; i < n; i ++)
{
cin >> k;
for(int i = 0; i < k; i ++) cin >> a[i], maxx = max(a[i],maxx);
//合并一个组,枚举相邻两个构造一个关系树
for(int i = 0; i < k - 1; i ++)
{
int x = find(a[i]), y = find(a[i + 1]);
if(x != y) p[x] = y, cnt[y] += cnt[x];
}
}
int ans = 0, sum = 0;//初始化根节点数量
for(int i = 1; i <= maxx; i ++)
{
if(i == find(i)) ans ++, sum += cnt[i];
}
cout << ans << " " << sum << endl;
cin >> q;
while(q --)
{
int x,y;
cin >> x >> y;
if(find(x) == find(y)) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}