Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
1.5 kB
0
Indexable
Never
// UniversumSets.cpp : Этот файл содержит функцию "main". Здесь начинается и заканчивается выполнение программы.

#include <iostream>
using namespace std;

void print(int* F, int* S, int N) {
    for (int i = 0; i < N; ++i) {
        cout << i << ' ' << F[i] << ' ' << S[i] << endl;
    }
    cout << endl << "######" << endl;
}

int search(int* F,int* S, int a) {
    int t = a; 
    int b = a;
    while (F[a] != a) {
        a = F[a];
    }
    while (F[t] != t) {
        b = t;
        t = F[t];
        F[b] = a;
    }
    return a;
}

void unions(int* F, int* S, int a, int b) {
    a = search(F, S, a);
    b = search(F, S, b);
    if (a == b) { return; }
    if (S[a] > S[b]) {int t = a; a = b; b = t;}
    F[a] = b;
    S[b] = S[a] + S[b];
}


int main()
{
    int N = 10;

    int* Fathers = new int[N];
    int* Sums = new int[N];
    for (int i = 0; i < N; ++i) {
        Fathers[i] = i;
        Sums[i] = 1;
    }

    print(Fathers, Sums, N);

    unions(Fathers, Sums, 5, 3);
    unions(Fathers, Sums, 2, 1);
    unions(Fathers, Sums, 6, 2);
    unions(Fathers, Sums, 7, 2);
    unions(Fathers, Sums, 6, 3);
    unions(Fathers, Sums, 9, 2);
    unions(Fathers, Sums, 6, 3);
    unions(Fathers, Sums, 7, 1);
    unions(Fathers, Sums, 0, 8);
    unions(Fathers, Sums, 4, 8);
    unions(Fathers, Sums, 8, 1);

    print(Fathers, Sums, N);
}