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

2024-01-06T18:45:09Z

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

New page

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

0478 - Ciclu - Revision history