0581 - Drumuri

Cerinţa

Se dă un graf orientat cu n noduri și un nod p. Să se afișeze toate nodurile q ale grafului, diferite de p, cu proprietatea că există cel puțin un drum de la p la q și lungimea drumului minim este pară.

Date de intrare

Programul citește de la tastatură numărul n de noduri, nodul p și numărul m de arce, iar apoi lista arcelor, formată din m perechi de forma i j, cu semnificația că există arc orientat de la nodul i la nodul j.

Date de ieșire

Programul va afișa pe ecran numărul C de noduri care respectă cerința, iar pe rândul următor cele C noduri, în ordine crescătoare, separate prin exact un spațiu.

Restricţii şi precizări

• 1 ≤ n ≤ 100
• prin drum minim se înțelege drum de cu lungimea minimă

Exemplu 1

Intrare

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

Iesire

Datele de intrare corespund restrictiilor impuse
3
1 4 6

Exemplu 2

Intrare

0 0 0

Iesire

Datele de intrare nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python" line> def verifica_restrictii(n, arce):

   # Verifică dacă datele de intrare respectă restricțiile
   if not (1 <= n <= 100) or not all(1 <= i <= n and 1 <= j <= n for i, j in arce):
       return False
   return True

def noduri_drum_par(n, p, arce):

   # Crează un dicționar pentru a stoca vecinii fiecărui nod
   vecini = {i: [] for i in range(1, n + 1)}
   for i, j in arce:
       vecini[i].append(j)

   # Inițializează distanțele de la nodul p la toate celelalte noduri
   dist = [float('inf')] * (n + 1)
   dist[p] = 0

   # Aplică algoritmul lui Dijkstra pentru a calcula distanțele minime
   vizitat = [False] * (n + 1)
   for _ in range(n):
       u = min((d, i) for i, d in enumerate(dist) if not vizitat[i])[1]
       vizitat[u] = True
       for v in vecini[u]:
           if dist[u] + 1 < dist[v]:
               dist[v] = dist[u] + 1

   # Determină nodurile care au un drum de lungime pară de la nodul p
   noduri = [i for i in range(1, n + 1) if i != p and dist[i] % 2 == 0]

   return noduri

def main():

   n, p, m = map(int, input().split())
   arce = [tuple(map(int, input().split())) for _ in range(m)]

   # Verifică dacă datele de intrare respectă restricțiile
   if not verifica_restrictii(n, arce):
       print("Datele de intrare nu corespund restrictiilor impuse")
       return

   print("Datele de intrare corespund restrictiilor impuse")

   # Determină nodurile care au un drum de lungime pară de la nodul p
   noduri = noduri_drum_par(n, p, arce)

   # Afiseaza rezultatul
   print(len(noduri))
   print(' '.join(map(str, sorted(noduri))))

if __name__ == "__main__":

   main()

</syntaxhighlight>