Code666 (代码贴、代码片段)

[C++] HDOJ1856 →→→→→进入此内容的聊天室

来自 , 2021-02-02, 写在 C++, 查看 129 次.
URL http://www.code666.cn/view/7ca57a9f
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. const int MAX=10000001;
  6. int father[MAX];//父节点
  7. int friend_X[MAX];//朋友数
  8. int Max;//最大朋友数
  9. using namespace std;
  10. void init()
  11. {
  12.     int i;
  13.     for(i=1;i<MAX;++i)
  14.     father[i]=i,friend_X[i]=1;//朋友数初始化都是1
  15. }
  16. int find_father(int x)//这里用递归省时，因为用while会超时，因为条件给的范围是一千万
  17. {
  18.     if(x!=father[x])//寻找父节点
  19.     father[x]=find_father(father[x]);
  20.     return father[x];
  21.     /*while(x!=father[x])//这里超时过一次，以后碰到数据大的最好不要用while
  22.     {
  23.         x=father[x];
  24.     }
  25.     return x;*/
  26. }
  27. void join_tree(int x,int y)
  28. {
  29.     int a,b;
  30.     a=find_father(x);
  31.     b=find_father(y);
  32.     if(a!=b)
  33.     {
  34.         father[a]=b;//把新的子节点并进父节点
  35.         friend_X[b]+=friend_X[a];//每次父节点都加上新的子节点的朋友数
  36.         if(friend_X[b]>Max)//挑选最大的父节点朋友数
  37.         Max=friend_X[b];
  38.     }
  39. }
  40. int main()
  41. {
  42.     int t,x,y,sum;
  43.     while(cin>>t)
  44.     {
  45.         init();
  46.         Max=1;//这里初始化是1不是0，因为当输入时0时，输出是1，就是这样我WA了一次
  47.         while(t--)
  48.         {
  49.             cin>>x>>y;
  50.             join_tree(x,y);//每次更新节点
  51.         }
  52.         cout<<Max<<endl;
  53.     }
  54.     return 0;
  55. }

回复 "HDOJ1856"

这儿你可以回复上面这条便签

captcha

贴代码片段 - Code666