Editing 4061 - Lant Q

= Cerinţa =
Se dă un graf neorientat cu n vârfuri și un număr natural <code>q</code>. Să se determine toate lanțurile elementare formate din cel puțin o muchie, cu extremitatea finală în vârful <code>q</code>.

= Date de intrare =
Fişierul de intrare <code>input.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>.

Pe ultima linie se află numărul <code>q</code>.

= Date de ieşire =
Fişierul de ieşire <code>output.txt</code> va conține, în ordine lexicografică, toate lanțurile elementare cu extremitatea finală în vârful <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. Dacă graful nu conține niciun lanț elementar format din cel puțin o muchie, cu extremitatea finală în vârful <code>q</code>, atunci se va afișa <code>NU EXISTA</code>.

= Restricţii şi precizări =

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

== Exemplul 1 ==
input.txt:

5 8

1 4 

1 3 

3 5 

4 5 

2 4 

1 2 

4 2 

3 4

5

output.txt:

1 2 4 3 5

1 2 4 5

1 3 4 5

1 3 5

1 4 3 5

1 4 5

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

3 1 2 4 5

3 1 4 5

3 4 5

3 5

4 1 3 5

4 2 1 3 5

4 3 5

4 5

== Exemplul 2 ==
input.txt:

99999 8

1 4 

1 3 

3 5 

4 5 

2 4 

1 2 

4 2 

3 4

5

Ouput:

Constraint violation: 1 ≤ n ≤ 20

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verify_constraints(n):
    if not (1 <= n <= 20):
        print("Constraint violation: 1 ≤ n ≤ 20 and 1 ≤ q ≤ n")
        exit()

def is_edge_chain(chain):
    for i in range(len(chain) - 1):
        if not graph[chain[i]][chain[i + 1]]:
            return False
    return True

def find_elementary_chains(v, end_vertex, path):
    path.append(v)
    if v == end_vertex and len(path) > 1:
        chains.append(path.copy())
    else:
        for neighbor in range(1, n + 1):
            if graph[v][neighbor] and neighbor not in path:
                find_elementary_chains(neighbor, end_vertex, path)
    path.pop()

def write_chains_to_file(chains, output_file):
    if not chains:
        output_file.write("NU EXISTA\n")
    else:
        chains.sort()
        for chain in chains:
            output_file.write(" ".join(map(str, chain)) + '\n')

if __name__ == "__main__":
    with open("input.txt", "r") as fin, open("output.txt", "w") as fout:
        n, m = map(int, fin.readline().split())
        
        verify_constraints(n)
        
        graph = [[False] * (n + 1) for _ in range(n + 1)]

        for _ in range(m):
            a, b = map(int, fin.readline().split())
            graph[a][b] = graph[b][a] = True

        end_vertex = int(fin.readline().strip())

        chains = []
        for start_vertex in range(1, n + 1):
            if start_vertex != end_vertex:
                find_elementary_chains(start_vertex, end_vertex, [])

        write_chains_to_file(chains, fout)

</syntaxhighlight>