题目描述
- 森林里的鸟
一些科学家为森林中成千上万的鸟类拍照。
假设所有出现在同一张照片中的鸟都属于同一棵树。
请你帮助科学家计算森林中树木的最大数量,对于任何一对鸟类,请判断它们是否在同一棵树上。
输入格式
第一行包含整数 N
表示照片数量。
接下来 N
行,每行描述一张照片,格式如下:
K B1 B2 … BK
K表示照片中的鸟的数量,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
(暴力枚举) $O(n^2)$
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e4 + 10;
int n, p[N], q, f[12];
int find(int x)
{
if(p[x] != x)p[x] = find(p[x]);
return p[x];
}
int main()
{
int M = 0;
cin >> n;
for (int i = 1; i <= N; i ++ )p[i] = i;
while (n -- )
{
int k;
cin >> k;
for (int i = 0; i < k; i ++ )
{
cin >> f[i];
M = max(M, f[i]);
}
for (int i = 1; i < k; i ++ )
{
if(find(f[i]) != find(f[i - 1]))p[find(f[i])] = find(f[i - 1]);
}
}
int ans;
ans = 0;
for (int i = 1; i <= M; i ++ )if(p[i] == i)ans ++ ;
cout << ans << " " << M << endl;
cin >> q;
while (q -- )
{
int a, b;
cin >> a >> b;
if(find(a) == find(b))printf("Yes\n");
else printf("No\n");
}
return 0;
}
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla