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

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()