View source for 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
<br>
== Exemplu 2 ==
; Intrare
 0
; Iesire
 Datele de intrare nu corespund restrictiilor impuse
<br>
== 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>