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

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