0475 - Lant

Cerinţa

Se dă lista muchiilor unui graf neorientat cu n vârfuri și două vârfuri p q. Să se determine toate lanțurile elementare cu extremitățile p și q.

Date de intrare

Fişierul de intrare lantIN.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 două numere p q.

Date de ieşire

Fişierul de ieşire lantOUT.txt va conține, în ordine lexicografică, toate lanțurile elementare cu extremitățile în p, respectiv 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.Î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 ≤ n

Exemplul 1:

lantIN.txt

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

lantOUT.txt

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 

Exemplul 2:

lantIN.txt

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

lantOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

def verifica_restrictii(n, muchii, p, q):
    if not (1 <= n <= 20):
        return False
    for u, v in muchii:
        if not (1 <= u <= n) or not (1 <= v <= n):
            return False
    if not (1 <= p <= n) or not (1 <= q <= n):
        return False
    return True

def citeste_graf(file_path):
    with open(file_path, 'r') as file:
        n, m = map(int, file.readline().split())
        muchii = [tuple(map(int, file.readline().split())) for _ in range(m)]

        try:
            p, q = map(int, file.readline().split())
        except ValueError:
            with open("lantOUT.txt", 'w') as file_out:
                file_out.write("Datele nu corespund restrictiilor impuse")
            exit()

    if not verifica_restrictii(n, muchii, p, q):
        with open("lantOUT.txt", 'w') as file_out:
            file_out.write("Datele nu corespund restrictiilor impuse")
        exit()

    return n, muchii, p, q

def dfs(v, tinta, graf, vizitat, path, rezultat):
    vizitat[v] = True
    path.append(v)

    if v == tinta:
        rezultat.append(path.copy())
    else:
        for vecin in graf[v]:
            if not vizitat[vecin]:
                dfs(vecin, tinta, graf, vizitat, path, rezultat)

    path.pop()
    vizitat[v] = False

def gaseste_lanturi(n, muchii, p, q):
    graf = {i: [] for i in range(1, n + 1)}
    for u, v in muchii:
        graf[u].append(v)
        graf[v].append(u)

    vizitat = {i: False for i in range(1, n + 1)}
    rezultat = []

    dfs(p, q, graf, vizitat, [], rezultat)

    rezultat = list(set(tuple(lant) for lant in rezultat))
    rezultat.sort()

    return rezultat

def scrie_lanturi(file_path, lanturi):
    with open(file_path, 'w') as file:
        for lant in lanturi:
            file.write(' '.join(map(str, lant)) + '\n')

if __name__ == "__main__":
    file_in = "lantIN.txt"
    file_out = "lantOUT.txt"

    n, muchii, p, q = citeste_graf(file_in)
    rezultat = gaseste_lanturi(n, muchii, p, q)
    scrie_lanturi(file_out, rezultat)