0478 - Ciclu

Cerinţa

Se dă lista muchiilor unui graf neorientat cu n vârfuri și un vârf p. Să se determine un ciclu elementar care conține vârful p.

Date de intrare

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

Date de ieşire

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

Restricţii şi precizări

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

Exemplul 1:

cicluIN.txt

5 8
1 4 
1 3 
3 5 
4 5 
2 4 
1 2 
4 2 
3 4
2

cicluOUT.txt

2 1 3 4 2

Exemplul 2:

cicluIN.txt

21 8
1 4 
1 3 
3 5 
4 5 
2 4 
1 2 
4 2 
3 4
2

cicluOUT.txt

"Datele nu corespund restrictiilor impuse"

Rezolvare

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()