4061 - Lant Q

Cerinţa

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

Date de intrare

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

Pe ultima linie se află numărul q.

Date de ieşire

Fişierul de ieşire output.txt va conține, în ordine lexicografică, toate lanțurile elementare cu extremitatea finală în vârful q, 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 q, atunci se va afișa NU EXISTA.

Restricţii şi precizări

• 1 ≤ n ≤ 20
• 1 ≤ q ≤ n
• 1 ≤ i, j ≤ n
• 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>