Rus Marius: Pagină nouă: == Enunț == Se știe că într-un graf neorientat conex, între oricare două vârfuri există cel putin un lanț iar lungimea unui lanț este egală cu numărul muchiilor care-l compun. Definim noțiunea lanț optim între două vârfuri `X` și `Y` ca fiind un lanț de lungime minimă care are ca extremități vârfurile `X` și `Y`. Este evident că între oricare două vârfuri ale unui graf conex vom avea unul sau mai multe la...

2024-01-06T21:39:45Z

Pagină nouă: == Enunț == Se știe că într-un graf neorientat conex, între oricare două vârfuri există cel putin un lanț iar lungimea unui lanț este egală cu numărul muchiilor care-l compun. Definim noțiunea lanț optim între două vârfuri <code>X</code> și <code>Y</code> ca fiind un lanț de lungime minimă care are ca extremități vârfurile <code>X</code> și <code>Y</code>. Este evident că între oricare două vârfuri ale unui graf conex vom avea unul sau mai multe la...

New page

== Enunț ==
Se știe că într-un graf neorientat conex, între oricare două vârfuri există cel putin un lanț iar lungimea unui lanț este egală cu numărul muchiilor care-l compun. Definim noțiunea lanț optim între două vârfuri <code>X</code> și <code>Y</code> ca fiind un lanț de lungime minimă care are ca extremități vârfurile <code>X</code> și <code>Y</code>. Este evident că între oricare două vârfuri ale unui graf conex vom avea unul sau mai multe lanțuri optime, depinzând de configurația grafului.

= Cerința =
Fiind dat un graf neorientat conex cu <code>N</code> vârfuri etichetate cu numerele de ordine <code>1</code>, <code>2</code>, …, <code>N</code> și două vârfuri ale sale notate <code>X</code> și <code>Y</code> (<code>1 ≤ X, Y ≤ N</code>, <code>X≠Y</code> ), se cere să scrieți un program care determină vârfurile care aparțin tuturor lanțurilor optime dintre <code>X</code> și <code>Y</code>.

= Date de intrare =
Fișierul de intrare <code>graf1.in</code> conține pe prima linie patru numere naturale reprezentând: <code>N</code> (numărul de vârfuri ale grafului), <code>M</code> (numărul de muchii), <code>X</code> și <code>Y</code> (cu semnificația din enunț). Pe următoarele <code>M</code> linii câte două numere naturale nenule <code>A[i], B[i]</code> (<code>1 ≤ A[i], B[i] ≤ N</code>, <code>A[i] ≠ B[i]</code>, pentru <code>1 ≤ i ≤ M</code> ) fiecare dintre aceste perechi de numere reprezentând câte o muchie din graf.

= Date de ieșire =
Fișierul de ieșire <code>graf1.out</code> va conține pe prima linie, numărul de vârfuri comune tuturor lanțurilor optime dintre <code>X</code> și <code>Y</code>; pe a doua linie, numerele corespunzătoare etichetelor acestor vârfuri, dispuse în ordine crescătoare; între două numere consecutive de pe această linie se va afla câte un spațiu.

= Restricții și precizări =

* <code>2 ≤ N ≤ 7500</code>
* <code>1 ≤ M ≤ 14000</code>

= Exemplul 1: =
<code>graf1.in</code>
6 7 1 4
1 2
1 3
1 6
2 5
3 5
5 6
5 4
<code>graf1.out</code>
3
1 4 5

= Exemplul 2: =
<code>graf1.in</code>
7501 7 1 4
1 2
1 3
1 6
2 5
3 5
5 6
5 4
<code>graf1.out</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from collections import deque

def check_constraints(n, m):
return 2 <= n <= 7500 and 1 <= m <= 14000

def bfs(start, dist, E):
for i in range(1, n + 1):
dist[i] = float('inf')

q = deque([start])
dist[start] = 0

while q:
nn = q.popleft()
for i in E[nn]:
if dist[i] == float('inf'):
dist[i] = dist[nn] + 1
q.append(i)

if __name__ == "__main__":
with open("graf1IN.txt", "r") as f:
n, m, x, y = map(int, f.readline().split())

if not check_constraints(n, m):
with open("graf1OUT.txt", "w") as g:
g.write("Datele nu corespund restrictiilor impuse")
exit()

E = [[] for _ in range(n + 1)]

for _ in range(m):
a, b = map(int, f.readline().split())
E[a].append(b)
E[b].append(a)

dist1 = [0] * (n + 1)
dist2 = [0] * (n + 1)
fr = [0] * (n + 1)
rez = []

bfs(x, dist1, E)
bfs(y, dist2, E)

for i in range(1, n + 1):
if dist1[i] + dist2[i] == dist1[y]:
fr[dist1[i]] += 1

for i in range(1, n + 1):
if dist1[i] != float('inf') and dist2[i] != float('inf') and dist1[y] != float('inf'):
if dist1[i] + dist2[i] == dist1[y] and fr[dist1[i]] == 1:
rez.append(i)

with open("graf1OUT.txt", "w") as g:
if rez:
g.write(str(len(rez)) + '\n')
g.write(" ".join(map(str, rez)))
else:
g.write("Nu exista noduri care sa corespunda conditiilor.")

</syntaxhighlight>

2165 - Graf 1 - Revision history