Editing 2123 - Relatii

== Enunt == 

<code>ar1<var2</code>

unde <code>var1</code> şi <code>var2</code> sunt două nume de variabile (deci litere mici distincte dintre primele <code>N</code> litere ale alfabetului englez).

= Cerința =
Scrieţi un program care să ordoneze crescător cele <code>N</code> variabile pe baza celor <code>M</code> relaţii cunoscute.

= Date de intrare =
Fişierul de intrare <code>relatiiIN.txt</code> conţine pe prima linie numerele naturale <code>N, M,</code> separate prin spaţiu. Pe fiecare dintre următoarele <code>M</code> linii este scrisă o relaţie sub forma din enunţ.

= Date de ieșire =
Fişierul de ieşire <code>relatiiOUT.txt</code> va conţine o singură linie pe care vor fi scrise <code>N</code> 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). În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =
• <code>2 ≤ N ≤ 10</code>

• <code>1 ≤ M ≤ 200</code>

• 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 <code>x1x2...xN</code> este mai mic din punct de vedere lexicografic decât şirul <code>y1y2...yN</code> dacă există un indice <code>k (1≤k≤N)</code> astfel încât <code>xi=yi</code>, pentru orice <code>1≤i<k</code> şi <code>xk<yk</code>.

= Exemplul 1: =
<code>relatiiIN.txt</code>
 4 5
 a<d
 a<c
 c>d
 b>c
 b>a
<code>relatiiOUT.txt</code>
 adcb

== Exemplul 2: ==
<code>relatiiIN.txt</code>
 4 5
 a<d
 a<c
 c>d
 b>c
 b>a
<code>relatiiOUT.txt</code>
 Datele nu corespund restrictiilor impuse.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verificare_restrictii(N, M):
    if not (2 <= N <= 10 and 1 <= M <= 200):
        with open("relatiiOUT.txt", "w") as fout:
            fout.write("Datele nu corespund restrictiilor impuse.\n")
        return False
    return True

def citire():
    with open("relatiiIN.txt", "r") as file:
        first_line = file.readline().strip()
        if not first_line:
            return None, None
        N, M = map(int, first_line.split())
        if not verificare_restrictii(N, M):
            return None, None
        R = [[0] * (N + 1) for _ in range(N + 1)]
        for _ in range(M):
            line = file.readline().strip()
            if not line:
               return None, None
            c1, c2, c3 = line[0], line[1], line[2]
            if c2 == '<':
                R[ord(c1) - ord('a') + 1][ord(c3) - ord('a') + 1] = -1
                R[ord(c3) - ord('a') + 1][ord(c1) - ord('a') + 1] = 1
            else:
                R[ord(c1) - ord('a') + 1][ord(c3) - ord('a') + 1] = 1
                R[ord(c3) - ord('a') + 1][ord(c1) - ord('a') + 1] = -1
    return N, R

def afisare(p):
    with open("relatiiOUT.txt", "w") as fout:
        for i in range(1, len(p)):
            fout.write(chr(p[i] - 1 + ord('a')))
        fout.write('\n')

def verif(p, R):
    for i in range(1, len(p)):
        for j in range(i + 1, len(p)):
            if R[p[i]][p[j]] == 1:
                return False
    return True

def main():
    N, R = citire()
    if N is None or R is None:
        return 
    p = list(range(N + 1))
    while True:
        if verif(p, R):
            break
        j = N - 1
        while p[j] > p[j + 1]:
            j -= 1
        i = N
        while p[i] < p[j]:
            i -= 1
        p[i], p[j] = p[j], p[i]
        st, dr = j + 1, N
        while st < dr:
            p[st], p[dr] = p[dr], p[st]
            st += 1
            dr -= 1
    afisare(p)

if __name__ == "__main__":
    main()

</syntaxhighlight>