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

d > c

c > d

iesire

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

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

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>