题目描述

一些科学家为森林中成千上万的鸟类拍照。

假设所有出现在同一张照片中的鸟都属于同一棵树。

请你帮助科学家计算森林中树木的最大数量，对于任何一对鸟类，请判断它们是否在同一棵树上。

输入格式
第一行包含整数 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

算法1

简单并查集，用set来存鸟的个数
因为没办法知道是哪些鸟
所以没办法正常初始化
采用 读入的时候判断是否初始化 如果没有就进行初始化

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
const int N = 1e4+10;
int p[N];
set<int> st;//鸟数量

int n,m;
int k,x;

int find(int x)
{
   return p[x] == x ? p[x] : p[x] = find(p[x]);
}

void merge(int x,int y)
{
   x = find(x);
   y = find(y);
   p[x] = y;
}


int main()
{
   cin>>n;
   for(int i=0;i<n;++i)
   {
      cin>>k;
      int tmp;
      cin>>tmp;
      if(p[tmp] == 0) p[tmp] = tmp;             //如果没有初始化，就是0所以进行初始化
      st.insert(tmp);
      for(int j=1;j<k;++j)
      {
         cin>>x;
         if(p[x] == 0) p[x] = x;
         st.insert(x);
         merge(tmp,x);
         tmp = x;
      }
   }
   cin>>m;
   int res = 0;
   for(int i=1;i<=N;++i) if(find(i) == i) res++;
   cout<<res<<" ";
   cout<<st.size()<<endl;
   for(int i=0;i<m;++i)
   {
      int a,b;
      cin>>a>>b;
      if(find(a) == find(b)) puts("Yes");
      else puts("No");
   }
   return 0;
}