HDU More is better

More is better

Time Limit:1000MS Memory Limit:102400KB 64bit IO Format:%I64d & %I64u Submit Status

Description

Mr Wang wants some boys to help him with a project. Because the project is rather complex, the more boys come, the better it will be. Of course there are certain requirements.Mr Wang selected a room big enough to hold the boys. The boy who are not been chosen has to leave the room immediately. There are 10000000 boys in the room numbered from 1 to 10000000 at the very beginning. After Mr Wang's selection any two of them who are still in this room should be friends (direct or indirect), or there is only one boy left. Given all the direct friend-pairs, you should decide the best way.

Input

The first line of the input contains an integer n (0 ≤ n ≤ 100 000) - the number of direct friend-pairs. The following n lines each contains a pair of numbers A and B separated by a single space that suggests A and B are direct friends. (A ≠ B, 1 ≤ A, B ≤ 10000000)

Output

The output in one line contains exactly one integer equals to the maximum number of boys Mr Wang may keep.

Sample Input

4
1 2
3 4
5 6
1 6
4
1 2
3 4
5 6
7 8

Sample Output

4
2

Hint

A and B are friends(direct or indirect), B and C are friends(direct or indirect), 
then A and C are also friends(indirect).

 In the first sample {1,2,5,6} is the result.
In the second sample {1,2},{3,4},{5,6},{7,8} are four kinds of answers.

[cpp] view plaincopyprint?

1. [cpp] view plaincopyprint?

   1. 簡單的並查集題目：

      WA了好幾次的代碼：

      [html] view plaincopyprint?
      1. #include
      2. #include
      3. using namespace std;
      4. int father[10000010];
      5. int num[10000010];
      6. int Max;
      7. int Find(int x)
      8. {
      9. if(x!=father[x])
      10. father[x]=Find(father[x]);
      11. return father[x];
      13. }
      14. void merset(int x,int y)
      15. {
      16. int q=Find(x);
      17. int p=Find(y);
      18. if(q!=p)
      19. {
      20. num[y]=num[x]+num[y];
      21. num[x]=num[y];
      22. if(num[x]>Max)
      23. Max=num[x];
      24. if(q>p)
      25. father[q]=p;
      26. else
      27. father[p]=q;
      28. }
      29. }
      30. void Init()
      31. {
      32. for(int i=1;i<=10000000;i++)
      33. {
      34. father[i]=i;
      35. num[i]=1;
      36. }
      37. }
      38. int main()
      39. {
      40. int n;
      41. while(~scanf("%d",&n))
      42. {
      44. Init();
      45. Max=num[1];
      46. while(n--)
      47. {
      48. int x,y;
      49. scanf("%d%d",&x,&y);
      50. merset(x,y);
      51. }
      52. cout< }
      55. return 0;
      56. }

          之後通過畫圖，單步跟蹤，還有請教學長終於找出了錯誤來源：

          
          

          x y 可以理解成當前要合並的兩個集合，但是他們又不一定不是兩個樹根 P Q則是find路徑壓縮後他們的樹根（可能是他們本身也可能是別的）他們兩個還有子樹指向它們，加X Y的數量 max就只能是他們子樹的數量加起來 而不是他們合並的那個最大數量。
          
          每次都只是更新了某個子樹上的全部數量 （第一次是准確的）但是根樹上的節點沒有再次更新。。。每次子樹變動 即合並的子節點不同 就會有損失。
          試下1 2 2 3 1 4 第一次更新num[1]=num[2]=2;第二次就是num[2]=num[3]=3;但此次num[1]還是2 第三次 就是num[1]=num[4]=3 ，損失了一個。。。
          
          
          如果一直更新根數 就是num[1]=num[2]=2,num[1]=num[3]=3;num[1]=num[4]=4。
          
          
          正確代碼： [cpp] view plaincopyprint?
          1. #include
          2. #include
          3. using namespace std;
          4. int father[10000010];
          5. int num[10000010];
          6. int Max;
          7. int Find(int x)
          8. {
          9. if(x!=father[x])
          10. father[x]=Find(father[x]);
          11. return father[x];
          13. }
          14. void merset(int x,int y)
          15. {
          16. int q=Find(x);
          17. int p=Find(y);
          18. if(q!=p)
          19. {
          20. num[p]=num[q]+num[p];
          21. num[q]=num[p];
          22. if(num[q]>Max)
          23. Max=num[q];
          24. if(q>p)
          25. father[q]=p;
          26. else
          27. father[p]=q;
          28. }
          29. }
          30. void Init()
          31. {
          32. for(int i=1;i<=10000000;i++)
          33. {
          34. father[i]=i;
          35. num[i]=1;
          36. }
          37. }
          38. int main()
          39. {
          40. int n;
          41. while(~scanf("%d",&n))
          42. {
          44. Init();
          45. Max=num[1];
          46. while(n--)
          47. {
          48. int x,y;
          49. scanf("%d%d",&x,&y);
          50. merset(x,y);
          51. }
          52. cout< }
          55. return 0;
          56. } [cpp] view plaincopyprint?
              1. 特別感謝浩浩學長的耐心指導~