Cod sursa(job #3190084)

Utilizator JeanM22ableecypm JeanM22 Data 6 ianuarie 2024 22:41:37
Problema Taramul Nicaieri Scor 0
Compilator py Status done
Runda Arhiva de probleme Marime 2.09 kb
# Harta "Taramului nicaieri" a fost pierduta, dar din fericire se mai stiu cateva date despre ea. Se stie ca exista N orase intre care se afla diferite drumuri. Drumurile "Taramului nicaieri" sunt un pic mai ciudate deoarece daca exista un drum care pleaca din orasul i si ajunge in orasul j nu exista in mod obligatoriu si un drum care pleaca din orasul j si ajunge in orasul i. De asemenea nu vor exista drumuri care pleaca si ajung in acelasi oras. Si nu vor exista mai multe drumuri identice(adica sa coincida si orasul din care pleaca si cel in care se ajunge).Pentru fiecare oras se stie cate drumuri pleaca din el si cate drumuri ajung in el.
#
# Cerinta
# Scrieti un program care determina drumurile de pe harta initiala.
#
# Date de Intrare
# Prima linie a fisierului de intrare harta.in contine numarul intreg N, reprezentand numarul de orase. Urmeaza apoi N linii, linia i continand doua numere x,y numarul de drumuri care pleaca din orasul i respectiv numarul de drumuri care intra in orasul i.
#
# Date de Iesire
# In fisierul harta.out veti afisa pe prima linie numarul M de drumuri construite, apoi vor urma M linii pe fiecare aflandu-se o pereche de numere a,b cu semnificatia exista un drum care pleaca din a si ajunge in b.
#
# Restrictii
# 1 ≤ N ≤ 100

inputFile = open("harta.in", "r")
outputFile = open("harta.out", "w")

from collections import deque

def solve():
    n = int(inputFile.readline())
    graph = [deque() for _ in range(n + 1)]
    degree = [0] * (n + 1)
    for i in range(1, n + 1):
        out, _in = map(int, inputFile.readline().split())
        degree[i] = out - _in

    start = [i for i in range(1, n + 1) if degree[i] > 0]
    if not start:
        start = [1]
    stack = start
    circuit = []

    while stack:
        node = stack[-1]
        if graph[node]:
            stack.append(graph[node].popleft())
        else:
            circuit.append(stack.pop())

    outputFile.write(str(len(circuit) - 1) + "\n")
    for i in range(len(circuit) - 2, -1, -1):
        outputFile.write(str(circuit[i + 1]) + " " + str(circuit[i]) + "\n")

solve()