4071 - Ciclu L

Cerinţa

Se dă lista muchiilor unui graf neorientat cu n noduri și un număr L. Să se determine un ciclu elementar de lungime L.

Date de intrare

Fişierul de intrare ciclulIN.txt conţine pe prima linie numerele n și m, reprezentând numărul de noduri 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 L.

Date de ieşire

Fişierul de ieşire ciclulOUT.txt va conține un singur ciclu elementar de lungime L. Acesta va începe și se va termina cu același nod.

Restricţii şi precizări

• 1 ≤ n ≤ 20
• 1 ≤ i , j ≤ n
• 1 ≤ L ≤ n
• pentru toate datele de test, va exista cel puțin un ciclu de lungime L
• lungimea unui ciclu este egală cu numărul de muchii.

Exemplul 1:

ciclulIN.txt

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

ciclulOUT.txt

3 5 4 6 3

Exemplul 2:

ciclulIN.txt

21 7
1 2
2 3
2 5
3 6
4 6
5 4
3 5
4

ciclulOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> N = 235

def check_constraints(n, m, k):

   if not (1 <= n <= 20) or not (1 <= m <= n*(n-1)//2) or not (1 <= k <= n):
       fout.write("Datele nu corespund restrictiilor impuse\n")
       exit(0)

def cond(j):

   if j > 1 and a[X[j-1]][X[j]] == 0:
       return 0
   if j == k and a[X[j]][X[1]] == 0:
       return 0
   return 1

def afis():

   for i in range(1, k+1):
       fout.write(str(X[i]) + " ")
   fout.write(str(X[1]) + '\n')
   exit(0)

def back(j):

   for i in range(1, n+1):
       if not p[i]:
           X[j] = i
           p[i] = 1
           if cond(j):
               if j == k:
                   afis()
               else:
                   back(j + 1)
           p[i] = 0

if __name__ == "__main__":

   fin = open("ciclulIN.txt", "r")
   fout = open("ciclulOUT.txt", "w")

   a = [[0] * 50 for _ in range(50)]
   n, m = map(int, fin.readline().split())

   check_constraints(n, m, n)  # Assuming k is the same as n

   for _ in range(m):
       x, y = map(int, fin.readline().split())
       a[x][y] = a[y][x] = 1

   k = int(fin.readline())
   check_constraints(n, m, k)

   X = [0] * 50
   p = [0] * 50

   back(1)

   fin.close()
   fout.close()

</syntaxhighlight>