Problema Graf – OJI 2006, Clasa a 11-a

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

Rezumat

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';
   return 0;
}

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