Problema Graf – OJI 2006, Clasa a 11-a

• Dificultate:
• Autor: Victor Mânz
• Online: InfoArena, PbInfo

Rezumat Graf

Se dă un graf neorientat conex, cu vârfurile etichetate de la $1$ la $n$, precum și două vârfuri distincte, notate cu $x$ și $y$. Trebuie să determinăm vârfurile care aparțin tuturor lanțurilor optime (de lungime minimă) dintre $x$ și $y$.

Soluție

Notăm cu $d(a, b)$ lungimea unui lanț optim între nodurile $a$ și $b$. Observăm că un nod $c$ aparține cel puțin unui lanț optim dintre $a$ și $b$ dacă și numai dacă $d(a, b) = d(a, c) + d(c, a)$. Mai mult, dacă nu mai există alte astfel de noduri $c'$, cu $d(a, c) = d(a, c')$, înseamnă că toate lanțurile optime de la $a$ la $b$ trec prin $c$.

Așadar, pentru a rezolva problema noastră, trebuie să căutăm toate nodurile ce îndeplinesc cele două condiții. Vom avea nevoie de niște parcurgeri în lățime pentru a calcula distanțele minime dintre noduri. O idee isteață este să facem doar două BFS-uri: Unul din $x$ și altul din $y$. Asta pentru că orice lanț de a cărui lungime avem nevoie are măcar o extremitate în $x$ sau în $y$. Ca să recapitulez:

1. Facem BFS din $x$ și din $y$, reținând rezultatele în vectorii dpX și dpY.
2. Pentru fiecare nod $i$, dacă dpX[i] + dpY[i] = dpX[y], incrementăm dpX[i] (numărul nodurilor ce se află pe un lanț optim și care sunt situate la distanța dpX[i] de $x$).
3. Parcurgem din nou nodurile pentru a vedea care au frq[dpX[i]] = 1. Acestea sunt nodurile ce aparțin tuturor lanțurilor optime dintre $x$ și $y$. Le adăugăm la vectorul ans.
4. Afișăm nodurile găsite la pasul anterior, precedate de numărul lor.

Sursă C++

#include <bits/stdc++.h>
using namespace std;

ifstream fin("graf.in");
ofstream fout("graf.out");

int main() {
    int n, m, x, y; fin >> n >> m >> x >> y;
    vector<vector<int>> ad(n + 1);
    for (int i = 0; i < m; i++) {
        int x, y; fin >> x >> y;
        ad[x].push_back(y);
        ad[y].push_back(x);
    }

    function<void(int, vector<int>&> bfs = [&](int src, vector<int>& dp) {
        fill(dp.begin(), dp.end(), -1);
        dp[src] = 0;
        queue<int> q; q.push(src);
        while (!q.empty()) {
            int node = q.front(); q.pop();
            for (int nghb : ad[node])
                if (dp[nghb] == -1) {
                    dp[nghb] = dp[node] + 1;
                    q.push(nghb);
                }
        }
    };
    vector<int> dpX(n + 1); bfs(x, dpX);
    vector<int> dpY(n + 1); bfs(y, dpY);

    vector<int> frq(n);
    for (int i = 1; i <= n; i++)
        if (dpX[i] + dpY[i] == dpX[y])
            frq[dpX[i]]++;
    vector<int> ans;
    for (int i = 1; i <= n; i++)
        if (dpX[i] + dpY[i] == dpX[y] && frq[dpX[i]] == 1)
            ans.push_back(i);

    fout << ans.size() << '\n';
    for (int node : ans)
        fout << node << ' ';
    fout << '\n';

    fout.close();
    return 0;
}

Dacă ai vreo nedumerire cu privire la problema Graf, lasă un comentariu și te voi ajuta

Îți place conținutul acestui site?

Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație!