Editing 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 &les; n &les; 100'''
* '''1 &les; i , j &les; 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 ==
<syntaxhighlight lang="python" line>
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()
</syntaxhighlight>