首页 > 代码库 > D 题
D 题
题目大意:
找朋友,最好把朋友最多的一堆的人数输出
运用并查集,每次更新最大数即可;
代码:
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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。