2165 - Graf 1

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 lanțuri optime, depinzând de configurația grafului.

Cerința

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

Date de intrare

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

Date de ieșire

Fișierul de ieșire graf1.out va conține pe prima linie, numărul de vârfuri comune tuturor lanțurilor optime dintre X și Y; 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

• 2 ≤ N ≤ 7500
• 1 ≤ M ≤ 14000

Exemplul 1:

graf1.in

6 7 1 4
1 2
1 3
1 6
2 5
3 5
5 6
5 4

graf1.out

3
1 4 5

Exemplul 2:

graf1.in

7501 7 1 4
1 2
1 3
1 6
2 5
3 5
5 6
5 4

graf1.out

Datele nu corespund restrictiilor impuse

Rezolvare

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.")