View source for 4071 - Ciclu L

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