首页 > 代码库 > hdu 1856 More is better
hdu 1856 More is better
http://acm.hdu.edu.cn/showproblem.php?pid=1856
这道题就是求一个集合里面最大的个数。 基本的并查集加一个步骤,将合并后的元素的个数保存在新的树根中。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 100010 5 using namespace std; 6 7 int f[maxn],a[maxn]; 8 int n,b,c; 9 int max1=-1; 10 11 int find1(int x) 12 { 13 if(x==f[x]) return x; 14 return f[x]=find1(f[x]); 15 } 16 17 void union1(int aa,int b) 18 { 19 int fa=find1(aa); 20 int fb=find1(b); 21 if(fa!=fb) 22 { 23 f[fa]=fb; 24 a[fb]+=a[fa]; 25 max1=max(max1,a[fb]); 26 } 27 } 28 29 void inti() 30 { 31 for(int i=0; i<=maxn; i++) 32 { 33 f[i]=i; 34 a[i]=1; 35 } 36 } 37 38 int main() 39 { 40 while(scanf("%d",&n)!=EOF) 41 { 42 inti(); 43 max1=1; 44 for(int i=0; i<n; i++) 45 { 46 scanf("%d%d",&b,&c); 47 union1(b,c); 48 } 49 printf("%d\n",max1); 50 } 51 return 0; 52 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。