0477 - Lanturi 1

Cerinţa

Se dă lista muchiilor unui graf neorientat cu n vârfuri și trei vârfuri p q r. Să se determine toate lanțurile elementare cu extremitățile în p și q care nu conțin vârful r.

Date de intrare

Fişierul de intrare lanturi1IN.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.

Următoarea linie conține trei numere p q r, cu semnificația precizată.

Date de ieşire

Fişierul de ieşire lanturi1OUT.txt va conține, în ordine lexicografică, toate lanțurile elementare cu extremitățile în p, respectiv q, care nu conțin vârful r , 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

• 1 ≤ n ≤ 20
• 1 ≤ i , j ≤n
• muchiile se pot repeta în fișierul de intrare
• 1 ≤ p , q , r ≤ n
• p, q și r sunt diferite

Exemplul 1:

lanturi1IN.txt

5 8
1 4 
1 3 
3 5 
4 5 
2 4 
1 2 
4 2 
3 4
2 5 3

lanturi1OUT.txt

2 1 4 5 
2 4 5 

Exemplul 2:

lanturi1IN.txt

100 100
1 4 
1 3 
3 5 
4 5 
2 4 
1 2 
4 2 
3 4
2 5 3

lanturi1OUT.txt

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>