0479 - Lant Maxim

Cerinţa

Se dă lista muchiilor unui graf neorientat cu n vârfuri și două vârfuri p q. Să se determine cel mai lung lanț elementar cu extremitățile p și q.

Date de intrare

Fişierul de intrare lantmaximIN.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 lantmaximOUT.txt va conține cel mai lung lanț elementar cu extremitățile p și q, vârfurile sale fiind separate prin exact un spațiu. Dacă sunt mai multe lanțuri de lungime maximă, se va afișa primul în ordine lexicografică.Î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
• pentru toate datele de test, va exista cel puțin un lanț cu extremitățile p q

Exemplul 1:

lantmaximIN.txt

5 7
1 4 
1 3 
3 5 
4 5 
1 2 
4 2 
3 4
2 5

lantmaximOUT.txt

2 1 3 4 5 

Exemplul 2:

lantmaximIN.txt

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

lantmaximOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

def citeste_graf(filename):
    try:
        with open(filename, 'r') as file:
            n, m = map(int, file.readline().split())
            graf = {}
            muchii = []
            for _ in range(m):
                i, j = map(int, file.readline().split())
                muchii.append((i, j))
                graf.setdefault(i, []).append(j)
                graf.setdefault(j, []).append(i)
            p, q = map(int, file.readline().split())
        return n, m, muchii, graf, p, q
    except ValueError:
        return None, None, None, None, None, None
    except FileNotFoundError:
        print(f"Fisierul {filename} nu a fost gasit.")
        return None, None, None, None, None, None
    except Exception as e:
        print(f"A aparut o eroare la citirea fisierului {filename}: {e}")
        return None, None, None, None, None, None

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

def dfs(graf, start, end, path, visited, results):
    visited[start] = True
    path.append(start)

    if start == end:
        results.append(path.copy())

    for neighbor in graf[start]:
        if not visited[neighbor]:
            dfs(graf, neighbor, end, path, visited, results)

    path.pop()
    visited[start] = False

def lanț_maxim(filename_in, filename_out):
    n, m, muchii, graf, p, q = citeste_graf(filename_in)
    
    if n is None:
        with open(filename_out, 'w') as file:
            file.write("Datele nu corespund restrictiilor impuse")
        return

    if not verifica_restrictii(n, m, muchii, p, q):
        with open(filename_out, 'w') as file:
            file.write("Datele nu corespund restrictiilor impuse")
        return

    visited = {v: False for v in graf}
    results = []

    dfs(graf, p, q, [], visited, results)

    if results:
        results.sort()
        result = results[0]

        with open(filename_out, 'w') as file:
            file.write(' '.join(map(str, result)))
    else:
        with open(filename_out, 'w') as file:
            file.write("Nu există lanț între vârfurile date")

def main():
    try:
        # Get input and output filenames from the user
        input_filename = input("Introduceți numele fișierului de intrare: ")
        output_filename = input("Introduceți numele fișierului de ieșire: ")

        # Call the lanț_maxim function with the provided filenames
        lanț_maxim(input_filename, output_filename)

        print(f"Rezultatele au fost scrise în {output_filename}")
    except Exception as e:
        print(f"A apărut o eroare: {e}")

if __name__ == "__main__":
    main()