Editing 0479 - Lant Maxim

= 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 cel mai lung lanț elementar cu extremitățile <code>p</code> și <code>q</code>.

= Date de intrare =
Fişierul de intrare <code>lantmaximIN.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>lantmaximOUT.txt</code> va conține cel mai lung lanț elementar cu extremitățile <code>p</code> și <code>q</code>, vârfurile sale fiind separate prin exact un spațiu. Dacă sunt mai multe lanțuri de lungime maximă, se va afișa primul în ordine lexicografică.Î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>
* pentru toate datele de test, va exista cel puțin un lanț cu extremitățile <code>p q</code>

= Exemplul 1: =
<code>lantmaximIN.txt</code>
 5 7
 1 4 
 1 3 
 3 5 
 4 5 
 1 2 
 4 2 
 3 4
 2 5
<code>lantmaximOUT.txt</code>
 2 1 3 4 5 

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

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def citeste_graf(filename):
    with open(filename, 'r') as file:
        try:
            n, m = map(int, file.readline().split())
            graf = {}
            muchii = []
            for _ in range(m):
                i, j = map(int, file.readline().split())
                muchii.append((i, j))
                if i not in graf:
                    graf[i] = []
                if j not in graf:
                    graf[j] = []
                graf[i].append(j)
                graf[j].append(i)
            p, q = map(int, file.readline().split())
        except ValueError:
            return None, None, None, None, None, None

    return n, m, muchii, graf, p, q

def verifica_restrictii(n, m, muchii, p, q):
    if not (1 <= n <= 20):
        return False
    for i, j in muchii:
        if not (1 <= i <= n) or not (1 <= j <= n):
            return False
    if not (1 <= p <= n) or not (1 <= q <= n):
        return False
    return True

def dfs(graf, start, end, path, visited, results):
    visited[start] = True
    path.append(start)

    if start == end:
        results.append(path.copy())

    for neighbor in graf[start]:
        if not visited[neighbor]:
            dfs(graf, neighbor, end, path, visited, results)

    path.pop()
    visited[start] = False

def lanț_maxim(filename_in, filename_out):
    n, m, muchii, graf, p, q = citeste_graf(filename_in)
    
    if n is None:
        with open(filename_out, 'w') as file:
            file.write("Datele nu corespund restrictiilor impuse")
        return

    if not verifica_restrictii(n, m, muchii, p, q):
        with open(filename_out, 'w') as file:
            file.write("Datele nu corespund restrictiilor impuse")
        return

    visited = {v: False for v in graf}
    results = []

    dfs(graf, p, q, [], visited, results)

    if results:
        results.sort()
        result = results[0]

        with open(filename_out, 'w') as file:
            file.write(' '.join(map(str, result)))
    else:
        with open(filename_out, 'w') as file:
            file.write("Nu există lanț între vârfurile date")

# Apelul funcției pentru datele din fișierul de intrare lantmaximIN.txt și scrierea rezultatului în lantmaximOUT.txt
lanț_maxim("lantmaximIN.txt", "lantmaximOUT.txt")

</syntaxhighlight>