0478 - Ciclu

Cerinţa

Se dă lista muchiilor unui graf neorientat cu n vârfuri și un vârf p. Să se determine un ciclu elementar care conține vârful p.

Date de intrare

Fişierul de intrare cicluIN.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 numărul p.

Date de ieşire

Fişierul de ieşire cicluOUT.txt va conține un singur ciclu elementar care conține vârful p. Acesta va începe și se va termina cu vârful p.Î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 ≤ n
• pentru toate datele de test, va exista cel puțin un ciclu care conține vârful p

Exemplul 1:

cicluIN.txt

5 8
1 4 
1 3 
3 5 
4 5 
2 4 
1 2 
4 2 
3 4
2

cicluOUT.txt

2 1 3 4 2

Exemplul 2:

cicluIN.txt

21 8
1 4 
1 3 
3 5 
4 5 
2 4 
1 2 
4 2 
3 4
2

cicluOUT.txt

"Datele nu corespund restrictiilor impuse"

Rezolvare

<syntaxhighlight lang="python3" line="1"> def check_restrictions(n, m, edges, p):

   # Check constraints
   if not (1 <= n <= 20):
       return False
   for i, j in edges:
       if not (1 <= i <= n) or not (1 <= j <= n):
           return False
   if not (1 <= p <= n):
       return False

   return True

def afis(k):

   global gasit
   for i in range(1, k + 1):
       fout.write(str(x[i]) + " ")
   fout.write(str(p) + " ")
   gasit = 1

def OK(k):

   if a[x[k - 1]][x[k]] != 1:
       return 0
   for i in range(1, k):
       if x[k] == x[i]:
           return 0
   return 1

def back(k):

   global gasit
   for i in range(1, n + 1):
       x[k] = i
       if not gasit and OK(k):
           if a[x[k]][p] == 1 and k > 2:
               afis(k)
           back(k + 1)

if __name__ == "__main__":

   fin = open("cicluIN.txt", "r")
   fout = open("cicluOUT.txt", "w")

   n, m = map(int, fin.readline().split())
   edges = [tuple(map(int, fin.readline().split())) for _ in range(m)]

   # Read the line and strip any leading or trailing whitespace
   p_line = fin.readline().strip()

   # Check if the line is not empty before converting to an integer
   if p_line:
       p = int(p_line)
   else:
       fout.write("Datele nu corespund restrictiilor impuse")
       fin.close()
       fout.close()
       exit()

   # Check restrictions
   if not check_restrictions(n, m, edges, p):
       fout.write("Datele nu corespund restrictiilor impuse")
   else:
       a = [[0] * (n + 1) for _ in range(n + 1)]

       for i, j in edges:
           a[i][j] = a[j][i] = 1

       x = [0] * 205
       gasit = 0

       x[1] = p
       back(2)

   fin.close()
   fout.close()

</syntaxhighlight>