Opis glavnog rešenja

Razmotrimo primer dat u tekstu zadatka: \(a/b = 1.5\), \(b/c = 2.0\), i \(d/e = 2.0\). Jednostavnom transformacijom dobijamo \(a = 1.5 \cdot b\), \(b = 2.0 \cdot c\), i \(d = 2.0 \cdot e\). Dalje, možemo primetiti da postoji odnos izmedju promenljivih, tj. da neke promenljive možemo da predstavimo preko neke druge promenljive uz odgovarajuću težinu. Preciznije, \(x\) i \(y\) su u odnosu sa težinom \(w\) ako važi \(x = w y\). Iz primera, \(a\) je u odnosu sa \(b\) sa težinom \(1.5\), \(b\) je u odnosu sa \(c\) sa težinom \(2.0\), \(d\) je u odnosu sa \(e\) sa težinom \(2.0\). Pored toga, primetimo da je \(a\) u odnosu sa \(c\) sa težinom \(1.5 \cdot 2.0\), jer možemo izraziti \(a\) preko \(c\) pomoću jednačine \(b = 2.0 \cdot c\) kao \(a = 1.5 \cdot 2.0 \cdot c\). Primetimo još da postoje neke promenljive koje nisu u odnosu, kao na primer \(a\) i \(e\).

Iz prethodnog razmatranja, dolazimo do ideje da promenljive možemo grupisati u disjunktne skupove po relaciji odnosa, tj. skup će biti sačinjen od promenljivih koje su međusobno u odnosu. Kako relacija odnosa uključuje i težine između promenljivih moramo modifikovati originalni algoritam disjunktnih skupova.

Za početak, razmotrimo koje promenljive mogu biti predstavnici skupova. Iz primera, vidimo da će u jednom skupu to biti promenljiva \(c\) (kako se \(a\) i \(b\) mogu predstaviti preko \(c\)), dok će u drugom skup to biti promenljiva \(e\) (kako se \(d\) može predstaviti preko \(e\)). Dakle, predstavnici skupova će biti one promenljive preko kojih se može predstaviti sve druge promenljive skupa.

Težine uključujemo tako što ćemo za promenljivu, uz informaciju o roditelju, čuvati i težinu sa kojom je ona u odnosu sa svojim roditeljem. Preciznije, ukoliko je \(x\) neki element i njegovor roditelj \(\pi_x\) sa težinom \(w_x\), onda važi \(x = w_x \pi_x\). Težine predstavnika skupova će biti \(1.0\), kako za nekog predstavnika skupa \(x\) važi da je on sam sebi roditelj, tj. \(x = \pi_x\), te \(x = 1.0 \cdot \pi_x\).

Dobijamo da za dve promenljive \(x\) i \(y\) za koje postoji put \(p = \langle x=x_1, x_2, \ldots, x_n=y \rangle\) važi \(x = w_{x_1} w_{x_2} \cdots w_{x_{n-1}} y\). Shodno tome, funkciju pronalaska predstavnika treba modifikovati tako da pored predstavnika vraća i proizvod svih težina na putu do predstavnika. To se slaže sa primerom, kako \(a = 1.5 \cdot 2.0 \cdot c\).

Pre nego što definišemo funkciju unije, prokomentarišimo kako će se struktura koristiti za izračunavanje vrednosti \(a / b\). Pomoću funkcije za pronalaženje predstavnika dobijamo odgovarajuće predstavnike \(f_a\) i \(f_b\) zajedno sa odgovarajućim težinama \(w_a\) i \(w_b\), tj. važi \(a = w_a f_a\) i \(b = w_b f_b\). Kako bi izračunali \(a / b = \frac{w_a f_a}{w_b f_b}\), predstavnici moraju biti isti i tada je \(a / b = w_a / w_b\). Ukoliko su predstavnici različiti \(a / b\) nije moguće izračunati jer tada \(a\) i \(b\) ne pripadaju istom skupu, tj. nisu u mođusobnom odnosu.

Da bi konstruisali disjunktne podskupove, prvo, za svaku promenljivu koja se javlja na ulazu napravimo jediničan skup koji kao predstavnika ima sam sebe i čija je težina \(1.0\). Nakon toga, za svaki odnos, sa ulaza, \(x / y = w\) pokrećemo uniju nad \(x\) i \(y\) sa težinom \(w\) (napomena: težinu \(w\) sada moramo uključiti pri izvršavanju unije). Uniju započinjemo tako što pronađemo predstavnike i odgovarajuće težine za \(x\) i \(y\), tada važi \(x = w_x f_x\) i \(y = w_y f_y\). Pored toga važi i \(x = w y\), jer važi \(x / y = w\) sa ulaza. Koristeći te činjenice dobijamo \(w_x f_x = w w_y f_y\). Iz čega u zavisnosti od toga da li roditelj od \(f_x\) postaje \(f_y\), ili roditelj od \(f_y\) postaje \(f_x\), dobijamo da je \(f_x = \frac{w w_y}{w_x} f_y\) i \(f_y = \frac{w_x}{w w_y} f_x\), respektivno. Drugim rečima, nove težine za \(f_x\) i \(f_y\) postaju \(\frac{w w_y}{w_x}\) i \(\frac{w_x}{w w_y}\), respektivno.

Složenost inicijalizacije jediničnih skupova zavisi od broja promenljivih na ulazu. U najgorem slučaju svaki od odnosa donosi po dve nove promenljive, te će složenost inicijalizacije jediničnih skupova biti \(O(n)\). Za svaki odnos sa ulaza, izvršavamo operaciju unije. Ako pretpostavimo da je operacija unije konstantne složenosti, onda složenost svih operacija unije možemo oceniti sa \(O(n)\). Za svaki upit, izvršavamo dva puta operaciju pronalaska predstavnika skupa, jednu proveru da li su predstavnici jednaki i jedno deljenje. Pod pretpostavkom da je operacija pronalska predstavnika skupa konstantne složenosti, složenost obrade svih upita je \(O(q)\). Ukupna složenost algoritma je \(O(n + q)\).

Dodatna napomena: Radi lakše implementacije disjunktnih skupova, koristimo mapu u kojoj se čuva promenljiva (niska) i odgovarajući identifikator (celi broj).

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

vector<pair<int, double>> base;
vector<int> rang;

void UF_init(int n) 
{
    base.resize(n);
    rang.resize(n);

    for (int i = 0; i < n; i++) {
        base[i] = { i, 1.0 };
        rang[i] = 0;
    }
}

// [fx, wx] = UF_find(x) --> x = wx * fx
pair<int, double> UF_find(int x) 
{
    if (x != base[x].first) {
        auto [fpx, wpx] = UF_find(base[x].first);

        base[x].first = fpx;
        base[x].second *= wpx;
    }

    return base[x];
}

void UF_union(int x, int y, double w) 
{
    auto [fx, wx] = UF_find(x);
    auto [fy, wy] = UF_find(y);

    if (fx == fy) return;

    if (rang[fx] < rang[fy]) {
        base[fx] = { fy, (w * wy) / wx };
    } else if (rang[fy] < rang[fx]) {
        base[fy] = { fx, wx / (w * wy) };
    } else {
        base[fx] = { fy, (w * wy) / wx }; 
        rang[fy]++;
    }
}

int main() 
{
    int n, q; cin >> n >> q;

    vector<tuple<string, string, double>> ratios(n);
    vector<pair<string, string>> queries(q);

    for (int i = 0; i < n; i++) {
        string x, y; double w;
        cin >> x >> y >> w;
        ratios[i] = { x, y, w };
    }

    for (int i = 0; i < q; i++) {
        string a, b;
        cin >> a >> b;
        queries[i] = { a, b };
    }

    int ind = 0;
    unordered_map<string, int> id;
    for (const auto &[x, y, _] : ratios) {
        if (id.find(x) == id.end()) {
            id[x] = ind++;
        }
        if (id.find(y) == id.end()) {
            id[y] = ind++;
        }
    }

    UF_init(id.size());

    for (const auto &[x, y, w] : ratios) {
        UF_union(id[x], id[y], w);
    }

    for (const auto &[a, b] : queries) {
        if (id.find(a) == id.end() || 
            id.find(b) == id.end()) {
            cout << -1 << " ";
            continue;
        }

        auto [fa, wa] = UF_find(id[a]);
        auto [fb, wb] = UF_find(id[b]);

        if (fa != fb) {
            cout << -1 << " ";
            continue;
        }

        cout << wa / wb << " ";
    }
    cout << endl;

    return 0;
}