Brianna Waltner: Pagină nouă: == 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...

2024-01-03T22:59:22Z

Pagină nouă: == 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...

New page

== 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>

0541 - Lant 1 - Revision history