Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <string.h>
- const int MaxLen = 10000;
- int LINK[10000] = {0};//Массив связей между элементами
- int RANG[10000] = {0};
- int find(int i) {
- if (LINK[i] == i){
- return i;
- }
- return LINK[i] = find(LINK[i]);
- }
- void unit(int p1,int p2) {
- p1 = find(p1);
- p2 = find(p2);
- if (p1 == p2) {
- return;
- }
- if (RANG[p1] == RANG[p2]) {
- RANG[p1]++;
- }
- if (RANG[p1] < RANG[p2]) {
- LINK[p2] = p1;
- } else {
- LINK[p1] = p2;
- }
- }
- int main() {
- //считываю строку s1,s1
- FILE *input = fopen("input.txt", "r");
- FILE *output = fopen("output.txt", "w");
- char S1[10000] = {0};//вышестоящая строка
- char S2[10000] = {0};//нижестоящая строка
- int k = 0;//количество уникальных комнат вышестоящей строки//количество уникальных комнат нижестоящей строки
- int p, p1, p2 = 0;
- int n = 0;
- int t = 0;
- int count = 0;
- int R1[10000] = {0};// номера комнат в s1
- int R2[10000] = {0};//номера комнат в s2
- int TEMP[10000] = {0};
- fgets(S1, MaxLen, input);
- for (int i = 0; i < MaxLen; ++i) {
- if (S1[i] == '\n') {
- break;
- }
- else{
- n++;
- }
- if ((S1[i] == ' ') && (S1[i - 1] != ' ')) {
- k++;
- count++;
- }
- if (S1[i] == ' ') {
- R1[i] = k;
- }else{
- R1[i] = 0;
- }
- }
- while(!feof(input)) {
- fgets(S2, MaxLen, input);
- for (int i = 0; i < n; i++) {
- if ((S2[i] == ' ') && (S2[i - 1] != ' ')) {
- k++;
- count++;
- }
- if (S2[i] == ' '){
- R2[i] = k;
- }
- else {
- R2[i] = 0;
- }
- }
- //COUNT ++ WHEN ADD ROOM
- for (int i = 0; i <= n; ++i) {
- LINK[i] = i;
- }
- for (int i = 0; i < n; ++i) {
- if ((R1[i] == 0) || (R2[i] == 0)) {
- continue;
- }
- p1 = find(R1[i]);//обращаемся к представителю
- p2 = find(R2[i]);
- if (p1 == p2) {
- continue;
- }
- --count;
- unit(p1, p2);//слияние
- }//сжатие комнат
- for (int i = 0; i < n; ++i) {
- TEMP[i] = 0;
- }
- k = 0;
- for (int i = 0; i < n; ++i) {
- if (R2[i] == 0) {
- continue;
- }
- p = find(R2[i]);
- if (TEMP[p] == 0) {
- TEMP[p] = ++k;
- }
- R2[i] = TEMP[p];
- }
- for (int i = 0; i < n; ++i) {
- R1[i] = R2[i];
- }
- k++;
- }
- fprintf(output,"%d",count);
- fclose(input);
- fclose(output);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement