0582 - Turneu

Un graf orientat se numește graf turneu dacă oricare ar fi două noduri diferite i, j, între ele există un singur arc: arcul (i j) sau arcul (j i). În orice graf turneu există un drum elementar care trece prin toate nodurile grafului.

Cerinţa

Se dă un graf turneu cu n noduri. Să se determine un drum elementar care să conțină toate nodurile grafului.

Date de intrare

Programul citește de la tastatură numărul de noduri n, iar apoi n*(n-1)/2 perechi i j, cu semnificația că există arcul (i j).

Date de ieșire

Programul va afișa pe ecran cele n noduri ale drumului determinat, separate prin exact un spațiu.

Restricţii şi precizări

• 1 ≤ n ≤ 100
• orice drum corect determinat este acceptat

Exemplu 1

Intrare

4
1 4
2 1
2 4
3 1
3 2
4 3

Iesire

Datele de intrare corespund restrictiilor impuse
1 4 3 2

Exemplu 2

Intrare

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 drum_elementar(n, 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)

   # Alege un nod de start arbitrar
   nod_curent = 1

   # Inițializează drumul cu nodul de start
   drum = [nod_curent]

   # Construiește drumul
   while len(drum) < n:
       for nod in sorted(vecini[nod_curent]):
           if nod not in drum:
               drum.append(nod)
               nod_curent = nod
               break

   return drum

def main():

   n = int(input())
   arce = [tuple(map(int, input().split())) for _ in range(n * (n - 1) // 2)]

   # 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ă un drum elementar care să conțină toate nodurile grafului
   drum = drum_elementar(n, arce)

   # Afiseaza rezultatul
   print(' '.join(map(str, drum)))

if __name__ == "__main__":

   main()

</syntaxhighlight>