Advertisement
Guest User

СНМ

a guest
Jul 10th, 2019
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.56 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <string.h>
  3.  
  4. const int MaxLen = 10000;
  5. int LINK[10000] = {0};//Массив связей между элементами
  6. int RANG[10000] = {0};
  7. int find(int i) {
  8. if (LINK[i] == i){
  9. return i;
  10. }
  11. return LINK[i] = find(LINK[i]);
  12. }
  13.  
  14. void unit(int p1,int p2) {
  15. p1 = find(p1);
  16. p2 = find(p2);
  17. if (p1 == p2) {
  18. return;
  19. }
  20. if (RANG[p1] == RANG[p2]) {
  21. RANG[p1]++;
  22. }
  23. if (RANG[p1] < RANG[p2]) {
  24. LINK[p2] = p1;
  25. } else {
  26. LINK[p1] = p2;
  27. }
  28. }
  29.  
  30. int main() {
  31. //считываю строку s1,s1
  32. FILE *input = fopen("input.txt", "r");
  33. FILE *output = fopen("output.txt", "w");
  34. char S1[10000] = {0};//вышестоящая строка
  35. char S2[10000] = {0};//нижестоящая строка
  36. int k = 0;//количество уникальных комнат вышестоящей строки//количество уникальных комнат нижестоящей строки
  37. int p, p1, p2 = 0;
  38. int n = 0;
  39. int t = 0;
  40. int count = 0;
  41. int R1[10000] = {0};// номера комнат в s1
  42. int R2[10000] = {0};//номера комнат в s2
  43. int TEMP[10000] = {0};
  44. fgets(S1, MaxLen, input);
  45. for (int i = 0; i < MaxLen; ++i) {
  46. if (S1[i] == '\n') {
  47. break;
  48. }
  49. else{
  50. n++;
  51. }
  52. if ((S1[i] == ' ') && (S1[i - 1] != ' ')) {
  53. k++;
  54. count++;
  55. }
  56. if (S1[i] == ' ') {
  57. R1[i] = k;
  58. }else{
  59. R1[i] = 0;
  60. }
  61. }
  62. while(!feof(input)) {
  63. fgets(S2, MaxLen, input);
  64. for (int i = 0; i < n; i++) {
  65. if ((S2[i] == ' ') && (S2[i - 1] != ' ')) {
  66. k++;
  67. count++;
  68. }
  69. if (S2[i] == ' '){
  70. R2[i] = k;
  71. }
  72. else {
  73. R2[i] = 0;
  74. }
  75. }
  76. //COUNT ++ WHEN ADD ROOM
  77. for (int i = 0; i <= n; ++i) {
  78. LINK[i] = i;
  79. }
  80. for (int i = 0; i < n; ++i) {
  81. if ((R1[i] == 0) || (R2[i] == 0)) {
  82. continue;
  83. }
  84. p1 = find(R1[i]);//обращаемся к представителю
  85. p2 = find(R2[i]);
  86. if (p1 == p2) {
  87. continue;
  88. }
  89. --count;
  90. unit(p1, p2);//слияние
  91. }//сжатие комнат
  92.  
  93. for (int i = 0; i < n; ++i) {
  94. TEMP[i] = 0;
  95. }
  96. k = 0;
  97. for (int i = 0; i < n; ++i) {
  98. if (R2[i] == 0) {
  99. continue;
  100. }
  101. p = find(R2[i]);
  102. if (TEMP[p] == 0) {
  103. TEMP[p] = ++k;
  104. }
  105. R2[i] = TEMP[p];
  106. }
  107.  
  108. for (int i = 0; i < n; ++i) {
  109. R1[i] = R2[i];
  110. }
  111. k++;
  112. }
  113.  
  114. fprintf(output,"%d",count);
  115.  
  116. fclose(input);
  117. fclose(output);
  118. return 0;
  119. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement