Advertisement
Guest User

Untitled

a guest
Nov 23rd, 2017
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.05 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. int32_t parent[100000];
  8. int32_t ans = 0;
  9.  
  10. void make_set(int v) {
  11. parent[v] = v;
  12. }
  13.  
  14. int find_set(int v) {
  15. if (v == parent[v])
  16. return v;
  17. return parent[v] = find_set(parent[v]);
  18. }
  19.  
  20. void union_sets(int a, int b) {
  21. a = find_set(a);
  22. b = find_set(b);
  23. if (a != b)
  24. {
  25. parent[b] = a;
  26. ans -= 1;
  27. }
  28. }
  29.  
  30. const int blocksize = 2000;
  31.  
  32. int main()
  33. {
  34. int32_t n = 0, m = 0;
  35. auto fin = fopen("input.bin", "rb");
  36. auto fout = fopen("output.bin", "wb");
  37. fread(reinterpret_cast<char *>(&n), 4, 1, fin);
  38. fread(reinterpret_cast<char *>(&m), 4, 1, fin);
  39. ans = n;
  40.  
  41. for (int i = 0; i < n; ++i)
  42. {
  43. make_set(i);
  44. }
  45.  
  46. int32_t a[blocksize];
  47.  
  48. for (int i = 0; i < m; i += blocksize)
  49. {
  50. fread(reinterpret_cast<char *>(&a), 4, min(blocksize, (m - i) * 2), fin);
  51. for (int j = 0; j < min(blocksize, (m - i) * 2); j += 2)
  52. {
  53. union_sets(a[j], a[j + 1]);
  54. }
  55. }
  56.  
  57. fwrite(&ans, 4, 1, fout);
  58.  
  59. fclose(fin);
  60. fclose(fout);
  61. return 0;
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement