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:
- Facem BFS din $x$ și din $y$, reținând rezultatele în vectorii
dpX
șidpY
. - Pentru fiecare nod $i$, dacă
dpX[i] + dpY[i] = dpX[y]
, incrementămdpX[i]
(numărul nodurilor ce se află pe un lanț optim și care sunt situate la distanțadpX[i]
de $x$). - 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 vectorulans
. - 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