Editing 2123 - Relatii

== Enunt == 

Să considerăm N variabile, denumite cu litere mici ale alfabetului englez, începând cu litera a. Să considerăm de asemenea M relaţii de ordine între aceste N variabile, sub forma:
var1>var2
sau
var1<var2
unde var1 şi var2 sunt două nume de variabile (deci litere mici distincte dintre primele N litere ale alfabetului englez).

== Cerința ==

Scrieţi un program care să ordoneze crescător cele N variabile pe baza celor M relaţii cunoscute.

== Date de intrare ==

Fişierul de intrare relatii.in conţine pe prima linie numerele naturale N, M, separate prin spaţiu. Pe fiecare dintre următoarele M linii este scrisă o relaţie sub forma din enunţ.

== Date de iesire == 

Fişierul de ieşire relatii.out va conţine o singură linie pe care vor fi scrise N litere mici, neseparate prin spaţii, reprezentând variabilele ordonate crescător. Dacă există mai multe soluţii posibile, se va afişa cea mai mică din punct de vedere lexicografic (prima în dicţionar).

== Restricții și precizări ==
* 2 ≤ N ≤ 10
* 1 ≤ M ≤ 200
* Relaţiile specificate în fişierul de intrare nu conţin spaţii.
* Pentru datele de test există întotdeauna soluţie, nu neapărat unică.
* Spunem că sirul x1x2...xN este mai mic din punct de vedere lexicografic decât şirul y1y2...yN dacă există un indice k (1≤k≤N) astfel încât xi=yi, pentru orice 1≤i<k şi xk<yk.

== Exemplul 1 ==

; intrare

:4 5
:a<d
:a<c
:c>d
:b>c
:b>a

; iesire 

:Datele introduse corespund rectrictiilor impuse. 

:adcb

== Exemplul 2 == 

; intrare

:10 3
:b>a
:c>a
:a<b
:b>a
:c>d

:Datele de intrare nu corespund restrictiilor impuse.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">

#2123 - Relatii

from collections import defaultdict

def ordonare_crescatoare(N, relatii):
    graf = defaultdict(list)
    indegree = {chr(ord('a') + i): 0 for i in range(N)}

    # Construirea grafului și calcularea gradelor de intrare
    for relatie in relatii:
        var1, semn, var2 = relatie
        graf[var1].append(var2)
        indegree[var2] += 1

    # Sortare topologică
    ordine_topologica = []
    stiva = [var for var, grad in indegree.items() if grad == 0]

    while stiva:
        nod = stiva.pop()
        ordine_topologica.append(nod)

        for vecin in graf[nod]:
            indegree[vecin] -= 1
            if indegree[vecin] == 0:
                stiva.append(vecin)

    # Verificare dacă există un ciclu (graful nu este aciclic)
    if len(ordine_topologica) != N:
        print("Ordin imposibil. Graful contine un ciclu.")
        return None

    return ordine_topologica

rezultat = ordonare_crescatoare(N, relatii)

if rezultat:
    print("Ordine crescatoare a variabilelor:", rezultat)
</syntaxhighlight>