0541 - Lant 1

Cerinţa

Se dă lista muchiilor unui graf neorientat și trei vârfuri p q r . Să se determine un lanț cu extremitățile p q care conține vârful r.

Date de intrare

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

Date de ieșire

Fişierul de ieşire lant1out.txt va conţine pe prima linie numărul de vârfuri din lanțul determinat. A doua linie va conține vârfurile din acest lanț, separate prin exact un spațiu.

Restricţii şi precizări

• 1 ⩽ n ⩽ 100
• 1 ⩽ i , j ⩽ n
• în fișierul de intrare muchiile se pot repeta;
• orice lanț cu extremitățile p q care conține vârful r și are lungimea mai mică decât 2*n este acceptat; lanțul nu trebuie să fie elementar
• pentru toate datele de test există cel puțin un lanț care respectă cerința;

Exemplul 1

lant1in.txt

8 5 7 3
1 2
1 3
1 5
2 3
2 5
2 7
3 6
4 6
4 7
5 7
6 8
7 8

lant1out.txt

Datele de intrare corespund restrictiilor impuse
5
5 1 3 2 7

Exemplu 2

lant1in.txt

5 1 2 3
1 2
2 3
3 4
4 5
5 1
1 1000001

lant1out.txt

Datele de intrare nu corespund restrictiilor impuse

Rezolvare

from collections import defaultdict


def bfs(graf, start):
    vizitat = [False] * (len(graf) + 1)
    coada = [start]
    vizitat[start] = True
    parinte = [-1] * (len(graf) + 1)

    while coada:
        nod = coada.pop(0)
        for vecin in graf[nod]:
            if not vizitat[vecin]:
                coada.append(vecin)
                vizitat[vecin] = True
                parinte[vecin] = nod

    return parinte


def construieste_lant(parinte, start, end):
    lant = []
    nod = end
    while nod != start:
        lant.append(nod)
        nod = parinte[nod]
    lant.append(start)
    return lant[::-1]


def main():
    with open('lant1in.txt', 'r') as f:
        n, p, q, r = map(int, f.readline().split())
        graf = defaultdict(list)
        muchii = []
        for _ in range(n-1):
            x, y = map(int, f.readline().split())
            muchii.append((x, y))
            graf[x-1].append(y-1)
            graf[y-1].append(x-1)

    m = len(muchii)
    if 1 <= n <= 100000 and 0 <= m <= n*(n-1)//2:
        print("Datele de intrare corespund restrictiilor impuse")
        parinte = bfs(graf, p-1)
        lant = construieste_lant(parinte, p-1, r-1)
        parinte = bfs(graf, r-1)
        lant += construieste_lant(parinte, r-1, q-1)[1:]
        with open('lant1out.txt', 'w') as f:
            f.write(str(len(lant)) + "\n")
            f.write(' '.join(map(str, [i+1 for i in lant])) + "\n")
    else:
        print("Datele de intrare nu corespund restrictiilor impuse")


if __name__ == "__main__":
    main()