Editing 0478 - Ciclu

= Cerinţa =
Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri și un vârf <code>p</code>. Să se determine un ciclu elementar care conține vârful <code>p</code>.

= Date de intrare =
Fişierul de intrare <code>cicluIN.txt</code> conţine pe prima linie numerele <code>n</code> și <code>m</code>, reprezentând numărul de vârfuri 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>p</code>.

= Date de ieşire =
Fişierul de ieşire <code>cicluOUT.txt</code> va conține un singur ciclu elementar care conține vârful <code>p</code>. Acesta va începe și se va termina cu vârful <code>p</code>.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricţii şi precizări =

* <code>1 ≤ n ≤ 20</code>
* <code>1 ≤ i , j ≤n</code>
* muchiile se pot repeta în fișierul de intrare
* <code>1 ≤ p ≤ n</code>
* pentru toate datele de test, va exista cel puțin un ciclu care conține vârful <code>p</code>

= Exemplul 1: =
<code>cicluIN.txt</code>
 5 8
 1 4 
 1 3 
 3 5 
 4 5 
 2 4 
 1 2 
 4 2 
 3 4
 2
<code>cicluOUT.txt</code>
 2 1 3 4 2

= Exemplul 2: =
<code>cicluIN.txt</code>
 21 8
 1 4 
 1 3 
 3 5 
 4 5 
 2 4 
 1 2 
 4 2 
 3 4
 2
<code>cicluOUT.txt</code>
 "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>