PAT甲级-1118 Birds in Forest (25 分)
发布日期:2022-02-10 08:11:02 浏览次数:5 分类:技术文章

本文共 926 字,大约阅读时间需要 3 分钟。

题目:
分析:并查集,和1107 social cluster很像,本题要在findFa函数中进行路径压缩,否则有一个测试点会超时,并查集还是要多练,太菜了
#include 
   
    #include
    
     #include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define MAX 999999999int n,m,k;int fa[10001];int bird[10001];int ans[10001];int findFa(int x){ 
           
   if(x == fa[x]) return x;
return fa[x] = findFa(fa[x]);}void uni(int a,int b){
   fa[findFa(a)] = findFa(b);}int main(){
   cin>>n;
for(int i = 1; i <= 10001;i++)
fa[i] = i;
int num = 0;
for(int i = 1; i <= n ;i++)
{
   int k;scanf("%d",&k);
int fro ;
for(int j = 0; j < k ; j++)
{
   int x;scanf("%d",&x);
if(j == 0)
fro = x;
else
uni(x,fro);
if(bird[x] == 0) num++;
bird[x] = 1;
}
}
int cnt = 0;
for(int i = 1; i <= 10001;i++)
if(fa[i] == i && bird[i] == 1)
cnt++;
cout< <<" "< <
cin>>k;
for(int i = 0 ; i < k ;i++)
{
   int a,b;cin>>a>>b;
if(findFa(a) == findFa(b))
cout<<"Yes\n";
else
cout<<"No\n";
}
return 0;}

转载地址:https://blog.csdn.net/qq_43567222/article/details/113916318 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:PAT甲级-1117 Eddington Number (25 分)
下一篇:PAT甲级-1095 Cars on Campus (30 分)

发表评论

最新留言

很好
[***.191.171.25]2022年08月19日 03时51分19秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章