Editing 0477 - Lanturi 1

= 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 nu conțin vârful <code>r</code>.

= Date de intrare =
Fişierul de intrare <code>lanturi1IN.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>lanturi1OUT.txt</code> va conține, în ordine lexicografică, toate lanțurile elementare cu extremitățile în <code>p</code>, respectiv <code>q</code>, care nu 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>lanturi1IN.txt</code>
 5 8
 1 4 
 1 3 
 3 5 
 4 5 
 2 4 
 1 2 
 4 2 
 3 4
 2 5 3
<code>lanturi1OUT.txt</code>
 2 1 4 5 
 2 4 5 

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

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def is_valid_edge(u, v, path, r, visited):
    return v != r and v not in path and not visited[v]

def generate_paths(graph, p, q, r, n):
    def backtrack(current, path, visited):
        visited[current] = True

        if current == q:
            result.append(path[:])
            visited[current] = False
            return

        for neighbor in graph[current]:
            if is_valid_edge(current, neighbor, path, r, visited):
                path.append(neighbor)
                backtrack(neighbor, path, visited)
                path.pop()

        visited[current] = False

    result = []
    visited = {i: False for i in range(1, n + 1)}
    backtrack(p, [p], visited)
    return result

def check_restrictions(n, m, edges, p, q, r):
    if not (1 <= n <= 20 and 1 <= p <= n and 1 <= q <= n and 1 <= r <= n and p != q != r):
        with open('lanturi1OUT.txt', 'w') as output_file:
            output_file.write("Datele nu corespund restrictiilor impuse\n")
        return False

    for edge in edges:
        u, v = edge
        if not (1 <= u <= n and 1 <= v <= n):
            with open('lanturi1OUT.txt', 'w') as output_file:
                output_file.write("Datele nu corespund restrictiilor impuse\n")
            return False

    return True

def main():
    with open('lanturi1IN.txt', 'r') as input_file:
        n, m = map(int, input_file.readline().split())
        edges = [tuple(map(int, input_file.readline().split())) for _ in range(m)]
        
        line = input_file.readline().split()
        if len(line) < 3:
            with open('lanturi1OUT.txt', 'w') as output_file:
                output_file.write("Datele nu corespund restrictiilor impuse\n")
            return

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

    if not check_restrictions(n, m, edges, p, q, r):
        return

    graph = {i: [] for i in range(1, n + 1)}
    for edge in edges:
        u, v = edge
        graph[u].append(v)
        graph[v].append(u)

    paths = generate_paths(graph, p, q, r, n)
    unique_paths = [list(item) for item in set(tuple(path) for path in paths)]
    unique_paths.sort()

    with open('lanturi1OUT.txt', 'w') as output_file:
        for path in unique_paths:
            output_file.write(" ".join(map(str, path)) + "\n")

if __name__ == "__main__":
    main()

</syntaxhighlight>