View source for 0475 - Lant

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

= Date de intrare =
Fişierul de intrare <code>lantIN.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 două numere <code>p q</code>.

= Date de ieşire =
Fişierul de ieşire <code>lantOUT.txt</code> va conține, în ordine lexicografică, toate lanțurile elementare cu extremitățile în <code>p</code>, respectiv <code>q</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 ≤ n</code>

= Exemplul 1: =
<code>lantIN.txt</code>
 5 8
 1 4 
 1 3 
 3 5 
 4 5 
 2 4 
 1 2 
 4 2 
 3 4
 2 5
<code>lantOUT.txt</code>
 2 1 3 4 5 
 2 1 3 5 
 2 1 4 3 5 
 2 1 4 5 
 2 4 1 3 5 
 2 4 3 5 
 2 4 5 

= Exemplul 2: =
<code>lantIN.txt</code>
 1000 100
 1 4 
 1 3 
 3 5 
 4 5 
 2 4 
 1 2 
 4 2 
 3 4
 2 5
<code>lantOUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_restrictii(n, muchii, p, q):
    if not (1 <= n <= 20):
        return False
    for u, v in muchii:
        if not (1 <= u <= n) or not (1 <= v <= n):
            return False
    if not (1 <= p <= n) or not (1 <= q <= n):
        return False
    return True

def citeste_graf(file_path):
    with open(file_path, 'r') as file:
        n, m = map(int, file.readline().split())
        muchii = [tuple(map(int, file.readline().split())) for _ in range(m)]

        try:
            p, q = map(int, file.readline().split())
        except ValueError:
            with open("lantOUT.txt", 'w') as file_out:
                file_out.write("Datele nu corespund restrictiilor impuse")
            exit()

    if not verifica_restrictii(n, muchii, p, q):
        with open("lantOUT.txt", 'w') as file_out:
            file_out.write("Datele nu corespund restrictiilor impuse")
        exit()

    return n, muchii, p, q

def dfs(v, tinta, graf, vizitat, path, rezultat):
    vizitat[v] = True
    path.append(v)

    if v == tinta:
        rezultat.append(path.copy())
    else:
        for vecin in graf[v]:
            if not vizitat[vecin]:
                dfs(vecin, tinta, graf, vizitat, path, rezultat)

    path.pop()
    vizitat[v] = False

def gaseste_lanturi(n, muchii, p, q):
    graf = {i: [] for i in range(1, n + 1)}
    for u, v in muchii:
        graf[u].append(v)
        graf[v].append(u)

    vizitat = {i: False for i in range(1, n + 1)}
    rezultat = []

    dfs(p, q, graf, vizitat, [], rezultat)

    rezultat = list(set(tuple(lant) for lant in rezultat))
    rezultat.sort()

    return rezultat

def scrie_lanturi(file_path, lanturi):
    with open(file_path, 'w') as file:
        for lant in lanturi:
            file.write(' '.join(map(str, lant)) + '\n')

if __name__ == "__main__":
    file_in = "lantIN.txt"
    file_out = "lantOUT.txt"

    n, muchii, p, q = citeste_graf(file_in)
    rezultat = gaseste_lanturi(n, muchii, p, q)
    scrie_lanturi(file_out, rezultat)

</syntaxhighlight>