首页 > 代码库 > D 题

D 题

2024-07-14 07:54:29   222人阅读

题目大意:
找朋友，最好把朋友最多的一堆的人数输出

 

运用并查集，每次更新最大数即可；

代码：

 1 #include <iostream> 2 #include <cstdio> 3 #include<cstring> 4 using namespace std; 5 #define N 300010 6 int fa[N],a,b; 7 int k[N]; 8 int getHead(int x) 9 {10     int a=x;11     while(x!=fa[x]) x=fa[x];12     fa[a]=x;13     return x;14 }15 void Union(int x,int y)16 {17     int fa_x=getHead(x);18     int fa_y=getHead(y);19     if(fa_x!=fa_y)20     {21         fa[fa_y]=fa_x;22         k[fa_x]+=k[fa_y];23     }24 }25 int main()26 {27     int T,n,m;28     cin>>T;29     while(T--){30 31         cin>>n>>m;32 33         for(int i=1;i<=n;i++) fa[i]=i;34         for(int i=1;i<=n;i++) k[i]=1;35         for(int i=0;i<m;i++){36             cin>>a>>b;37             Union(a,b);38         }39         int maxn=k[1];40         for(int i=2;i<=n;i++)41         {42             if(k[i]>maxn) maxn=k[i];43             //cout<<k[i]<<‘ ‘;44         }45 46         cout<<maxn<<endl;47     }48     return 0;49 }

 


联系
我们