PAT甲级-1118 Birds in Forest (25 分)-白红宇的个人博客

发布日期：2022-02-10 08:11:02 浏览次数：19 分类：技术文章

本文共 917 字，大约阅读时间需要 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<
           
            <<" "<
            
             <
             
              >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 分)

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

题目：

分析：并查集，和1107 social cluster很像，本题要在findFa函数中进行路径压缩，否则有一个测试点会超时，并查集还是要多练，太菜了

发表评论

最新留言

关于作者

推荐文章