Editing 0476 - Lanturi

= Cerinţa =
Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri și trei vârfuri <code>p q r</code>. Să se determine toate lanțurile elementare cu extremitățile în <code>p</code> și <code>q</code> care conțin vârful <code>r</code>.

= Date de intrare =
Fişierul de intrare <code>lanturiIN.txt</code> conţine pe prima linie numerele <code>n</code> și <code>m</code>, reprezentând numărul de vârfuri ale grafului și numărul de muchii date în continuare. Fiecare dintre următoarele <code>m</code> linii conține câte o pereche de numere <code>i j</code>, cu semnificația că există muchie între <code>i</code> și <code>j</code>.

Următoarea linie conține trei numere <code>p q r</code>, cu semnificația precizată.

= Date de ieşire =
Fişierul de ieşire <code>lanturiOUT.txt</code> va conține, în ordine lexicografică, toate lanțurile elementare cu extremitățile în <code>p</code>, respectiv <code>q</code>, care conțin vârful <code>r</code>, fiecare lanț fiind afișat pe câte o linie a fișierului, vârfurile dintr-un lanț fiind separate prin exact un spațiu.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricţii şi precizări =

* <code>1 ≤ n ≤ 20</code>
* <code>1 ≤ i , j ≤n</code>
* muchiile se pot repeta în fișierul de intrare
* <code>1 ≤ p , q , r ≤ n</code>
* <code>p</code>, <code>q</code> și <code>r</code> sunt diferite

= Exemplul 1: =
<code>lanturiIN.txt</code>
 5 8
 1 4 
 1 3 
 3 5 
 4 5 
 2 4 
 1 2 
 4 2 
 3 4
 2 5 3
<code>lanturiOUT.txt</code>
 2 1 3 4 5 
 2 1 3 5 
 2 1 4 3 5 
 2 4 1 3 5 
 2 4 3 5 

= Exemplul 2: =
<code>lanturiIN.txt</code>
 100 100
 1 4 
 1 3 
 3 5 
 4 5 
 2 4 
 1 2 
 4 2 
 3 4
 2 5 3
<code>lanturiOUT.txt</code>
 Nu corespunde restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def gaseste_lanturi_elementare(graph, p, q, r):
    def dfs(curent, cale):
        nonlocal rezultat
        vizitat[curent] = True
        cale.append(curent)

        if curent == q:
            if r in cale:
                rezultat.add(tuple(cale))
        else:
            for vecin in graph[curent]:
                if not vizitat[vecin]:
                    dfs(vecin, cale)

        vizitat[curent] = False
        cale.pop()

    rezultat = set()
    vizitat = [False] * (n + 1)
    dfs(p, [])

    return rezultat

def verifica_restrictii(n, p, q, r):
    if not (1 <= n <= 20) or not (1 <= p <= n) or not (1 <= q <= n) or not (1 <= r <= n) or p == q or p == r or q == r:
        return False
    return True

def citeste_intrare(nume_fisier):
    with open(nume_fisier, 'r') as fisier:
        try:
            n, m = map(int, fisier.readline().split())
            graf = {i: [] for i in range(1, n + 1)}

            for _ in range(m):
                linie = fisier.readline().split()
                if len(linie) != 2:
                    raise ValueError("Nu corespunde restrictiilor impuse")
                i, j = map(int, linie)
                graf[i].append(j)
                graf[j].append(i)

            linie = fisier.readline().split()
            if len(linie) != 3:
                raise ValueError("Nu corespunde restrictiilor impuse")

            p, q, r = map(int, linie)

            if not (1 <= p <= n) or not (1 <= q <= n) or not (1 <= r <= n) or p == q or p == r or q == r:
                raise ValueError("Nu corespunde restrictiilor impuse")

        except ValueError as e:
            with open('lanturiOUT.txt', 'w') as fisier_iesire:
                fisier_iesire.write(f"Nu corespunde restrictiilor impuse")
            exit()

    return n, graf, p, q, r

def scrie_iesire(nume_fisier, lanturi):
    with open(nume_fisier, 'w') as fisier:
        if lanturi == "Nu corespunde restricțiilor impuse":
            fisier.write(lanturi)
        else:
            for lant in lanturi:
                fisier.write(' '.join(map(str, lant)) + '\n')

if __name__ == '__main__':
    fisier_intrare = 'lanturiIN.txt'
    fisier_iesire = 'lanturiOUT.txt'

    n, graf, p, q, r = citeste_intrare(fisier_intrare)

    if not verifica_restrictii(n, p, q, r):
        scrie_iesire(fisier_iesire, "Nu corespunde restrictiilor impuse")
    else:
        lanturi = gaseste_lanturi_elementare(graf, p, q, r)
        lanturi = [list(lant) for lant in lanturi]
        lanturi.sort()

        scrie_iesire(fisier_iesire, lanturi)

</syntaxhighlight>