4071 - Ciclu L
De la Universitas MediaWiki
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
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()