共计 1093 个字符,预计需要花费 3 分钟才能阅读完成。
题目粗心
当初有 N 张图片,每一张图片外面有 K 只鸟,在同一张图片中的鸟属于同一棵树,计算森林中树木的最大数目,并且对于任意一对鸟,判断是否在同一棵树上。
算法思路
本题考查并查集的利用,咱们应用 set 汇合 birds 保留所有的输出的鸟,并在输出每一张图片的时候,将其中所有的鸟进行合并为一组,而后对于 birds 中所有的鸟类依据其先人归并为一棵树,并存放到 set 汇合 trees 中,最初对于任意两个鸟的编号,只须要比拟 father 数组的值是否雷同即可。
留神点
- 1、查找 father 的办法得应用门路压缩,不然会有一个测试点超时。
提交后果
AC 代码
#include<cstdio>
#include<algorithm>
#include<unordered_set>
#include<vector>
using namespace std;
unordered_set<int> birds;
unordered_set<int> trees;
int father[10005];
int findFather(int x){
int a = x;
while(x!=father[x]){x = father[x];
}
while (a!=father[a]){int z = father[a];
father[a] = x;
a = z;
}
return x;
}
void Union(int a,int b){int fa = findFather(a);
int fb = findFather(b);
if(fa!=fb){father[fa] = fb;
}
}
int main() {for(int i=0;i<=10000;++i){father[i] = i;
}
int n;
scanf("%d",&n);
for(int i=0;i<n;++i){
int k;
scanf("%d",&k);
vector<int> t(k);
for(int j=0;j<k;++j){scanf("%d",&t[j]);
birds.insert(t[j]);
if(j!=0){Union(t[j],t[j-1]);
}
}
}
for(auto it:birds){int f=findFather(it);
trees.insert(f);
}
printf("%lu %lu\n",trees.size(),birds.size());
int query;
scanf("%d",&query);
for(int i=0;i<query;++i){
int a,b;
scanf("%d %d",&a,&b);
if(father[a]==father[b]){printf("Yes\n");
}else{printf("No\n");
}
}
return 0;
}
正文完