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

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()