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

2024-01-06T18:49:54Z

Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat cu <code>n</code> noduri și un număr <code>L</code>. Să se determine un ciclu elementar de lungime <code>L</code>. = Date de intrare = Fişierul de intrare <code>ciclulIN.txt</code> conţine pe prima linie numerele <code>n</code> și <code>m</code>, reprezentând numărul de noduri ale grafului și numărul de muchii date în continuare. Fiecare dintre următoarele <code>m</code> linii conține câte o pereche de nu...

New page

= Cerinţa =
Se dă lista muchiilor unui graf neorientat cu <code>n</code> noduri și un număr <code>L</code>. Să se determine un ciclu elementar de lungime <code>L</code>.

= Date de intrare =
Fişierul de intrare <code>ciclulIN.txt</code> conţine pe prima linie numerele <code>n</code> și <code>m</code>, reprezentând numărul de noduri ale grafului și numărul de muchii date în continuare. Fiecare dintre următoarele <code>m</code> linii conține câte o pereche de numere <code>i j</code>, cu semnificația că există muchie între <code>i</code> și <code>j</code>.

Următoarea linie conține numărul <code>L</code>.

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

= Restricţii şi precizări =

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

= Exemplul 1: =
<code>ciclulIN.txt</code>
6 7
1 2
2 3
2 5
3 6
4 6
5 4
3 5
4
<code>ciclulOUT.txt</code>
3 5 4 6 3

= Exemplul 2: =
<code>ciclulIN.txt</code>
21 7
1 2
2 3
2 5
3 6
4 6
5 4
3 5
4
<code>ciclulOUT.txt</code>
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>

4071 - Ciclu L - Revision history