Advertisement
Guest User

Untitled

a guest
May 29th, 2015
230
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.20 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <map>
  5. #include <queue>
  6. #include <algorithm>
  7. #include <cmath>
  8. #include <fstream>
  9. #include <cstdlib>
  10.  
  11. using namespace std;
  12.  
  13. typedef long long lol;
  14.  
  15. int n;
  16.  
  17. struct snow
  18. {
  19. int pred;
  20. int x;
  21. int y;
  22. };
  23.  
  24. snow a[10000];
  25. bool comp[10000];
  26.  
  27. int find_p(int x)
  28. {
  29. if (a[x].pred == x)
  30. return x;
  31. else
  32. return a[x].pred = find_p(a[x].pred);
  33. }
  34.  
  35. void union_p(int x, int y)
  36. {
  37. int t = rand() % 2;
  38. if (t == 0)
  39. swap(x, y);
  40. a[x].pred = find_p(y);
  41. return;
  42. }
  43.  
  44. int main()
  45. {
  46. scanf("%d", &n);
  47. for (int i = 0; i<n; i++)
  48. {
  49. int x, y;
  50. scanf("%d%d", &x, &y);
  51. a[i].pred = i;
  52. a[i].x = x;
  53. a[i].y = y;
  54. }
  55. for (int i = 0; i<n-1; i++)
  56. for (int j = i+1; j<n; j++)
  57. {
  58. if (a[i].x == a[j].x || a[i].y == a[j].y)
  59. if (find_p(i) != find_p(j))
  60. union_p(i,j);
  61. }
  62. int k = 0;
  63. for (int i = 0; i<n; i++)
  64. if (comp[find_p(i)] == 0)
  65. {
  66. k++;
  67. comp[find_p(i)] = 1;
  68. }
  69. printf("%d", k-1);
  70. return 0;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement