Prosečan broj klikova

Nedavno je otkriveno da je na Internetu u proseku potrebno 19 klikova da bi se sa bilo koje stranice došlo do bilo koje druge.

Opis ulaza

Sa standardnog ulaza se učitava broj stranica na mreži \(n\), a zatim i broj linkova \(m\). U narednih \(m\) linija se učitavaju linkovi \(a_i \to b_i\) tako što je prvo navedena polazna stranica \(a_i\), a zatim i dolazna stranica \(b_i\). Pretpostaviti da stranice neće sadržati linkove na same sebe, kao i da će svaka dva para stranica međusobno biti dostižna.

Opis izlaza

Na standardni izlaz za datu mrežu ispisati prosečan broj klikova da bi se sa bilo koje stranice došlo do bilo koje druge. Ne razmatrati klikove sa stranice na samu sebe, kako ni klikove između nedostižnih stranica. Ukoliko ne postoji nijedan klik između različitih stranica, ispisati -1.

Primer

Ulaz

Izlaz

Objašnjenje

Ukupno imamo \(0 + 1 + 1 + 2 + 1 + 0 + 2 + 1 + 3 + 0 = 11\) klikova između svih parova različitih stranica, a pošto imamo \(n(n-1) = 4 \cdot (4 -1) =12\) parova različitih stranica, prosečan broj klikova je \(\frac{11}{12} \approx \text{1.833}\).

Rešenje

Rešenje preko Flojd-Varšalovog algoritma

Da bismo izračunali prosečan broj klikova između svih parova stranica, možemo koristiti Flojd-Varšalov algoritam koji nam omogućava da pronađemo najkraće puteve između svih parova čvorova u grafu. Nakon što dobijemo matricu rastojanja između svih parova stranica, možemo izračunati ukupan zbir klikova. Kako znamo da imamo \(n(n-1)\) parova različitih stranica (koje su dostižne međusobno po uslovu zadatka), prosečan broj klikova će biti zbir klikova podeljen sa \(n(n-1)\).

Složenost Flojd-Varšalovog algoritma je \(O(n^3)\).

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

typedef vector<vector<int>> Matrix;

#define INF (numeric_limits<int>::max())

class Graph
{
    private:
        int broj_cvorova;
        Matrix W, D;

    public:
        Graph(int n) : broj_cvorova(n)
                     , W(n, vector<int>(n, INF))
                     , D(n, vector<int>(n, INF))
        {
            for (int i = 0; i < n; i++) {
                W[i][i] = 0;
            }
        }

        void addEdge(int u, int v)
        {
            W[u][v] = 1;
        }

        double averageClicks()
        {
            floyd_warshall();

            int sum = 0;
            for (int u = 0; u < broj_cvorova; u++) {
                for (int v = 0; v < broj_cvorova; v++) {
                    if (u != v && D[u][v] != INF) {
                        sum += D[u][v];
                    }
                }
            }

            return sum / (double) (broj_cvorova * (broj_cvorova - 1));
        }
    
    private:
        void floyd_warshall()
        {
            D = W;
            for (int k = 0; k < broj_cvorova; k++) {
                for (int i = 0; i < broj_cvorova; i++) {
                    for (int j = 0; j < broj_cvorova; j++) {
                        if (D[i][k] != INF && D[k][j] != INF &&
                            D[i][j] > D[i][k] + D[k][j]) {
                            D[i][j] = D[i][k] + D[k][j];
                        }
                    }
                }
            }
        }
};

int main(void) 
{
    int n, m; cin >> n >> m;

    Graph g(n);

    for (int i = 0; i < m; i++) {
        int x, y; cin >> x >> y;
        g.addEdge(x - 1, y - 1);
    }


    cout << g.averageClicks() << endl;

    return 0;
}

Rešenje preko BFS algoritma

Drugi pristup je da za svaku stranicu pokrenemo BFS algoritam koji nam omogućava da pronađemo najkraće puteve od te stranice do svih ostalih. Na ovaj način ćemo dobiti zbir klikova od svake stranice do svih ostalih, i na kraju ćemo izračunati prosečan broj klikova kao zbir svih klikova podeljen sa \(n(n-1)\).

Složenost ovog pristupa je \(O(n (n + m))\), gde je \(n\) broj stranica, a \(m\) broj linkova, što može biti efikasnije za retke grafove u poređenju sa Flojd-Varšalovim algoritmom.

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

#define INF (numeric_limits<int>::max())

class Graph
{
    private:
        int broj_cvorova;
        vector<vector<int>> susedi;
        vector<int> udaljenost;

    public:
        Graph(int n) : broj_cvorova(n)
                     , susedi(n)
                     , udaljenost(n)
        {}

    void addEdge(int u, int v)
    {
        susedi[u].push_back(v);
    }

    double averageClicks() 
    {
        int sum = 0;
        for (int u = 0; u < broj_cvorova; u++) {
            BFS(u);

            for (int v = 0; v < broj_cvorova; v++) {
                if (u != v && udaljenost[v] != INF) {
                    sum += udaljenost[v];
                }
            }
        }

        return sum / (double) (broj_cvorova * (broj_cvorova - 1));
    }

    private:
        void BFS(int start)
        {
            fill(udaljenost.begin(), udaljenost.end(), INF);
            udaljenost[start] = 0;

            queue<int> q;
            q.push(start);

            while (!q.empty()) {
                int u = q.front();
                q.pop();

                for (int v : susedi[u]) {
                    if (udaljenost[v] == INF) {
                        udaljenost[v] = udaljenost[u] + 1;
                        q.push(v);
                    }
                }
            }
        }
};

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

    Graph g(n);

    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        g.addEdge(u - 1, v - 1);
    }

    cout << g.averageClicks() << endl;

    return 0;
}