Rus Marius: Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat cu `n` vârfuri și mai multe șiruri de vârfuri din graf. Să se verifice despre fiecare șir dacă reprezintă un lanț. În caz afirmativ, să se precizeze dacă este elementar. = Date de intrare = Fişierul de intrare `veriflantIN.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....

2023-12-30T12:37:10Z

Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri și mai multe șiruri de vârfuri din graf. Să se verifice despre fiecare șir dacă reprezintă un lanț. În caz afirmativ, să se precizeze dacă este elementar. = Date de intrare = Fişierul de intrare <code>veriflantIN.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....

New page

= Cerinţa =
Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri și mai multe șiruri de vârfuri din graf. Să se verifice despre fiecare șir dacă reprezintă un lanț. În caz afirmativ, să se precizeze dacă este elementar.

= Date de intrare =
Fişierul de intrare <code>veriflantIN.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>.

Urmează numărul de șiruri <code>k</code>. Pentru fiecare șir se dă numărul de vârfuri și apoi vârfurile.

= Date de ieşire =
Fişierul de ieşire <code>veriflantOUT.txt</code> va conține <code>k</code> linii. Fiecare linie va contine unul dintre cuvintele <code>NU</code>, <code>ELEMENTAR</code>, <code>NEELEMENTAR</code>, după cum șirul de vârfuri corespunzător nu formează lanț, formează lanț elementar, respectiv formează lanț neelementar.Î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 ≤ 100</code>
* <code>1 ≤ i , j ≤ n</code>
* muchiile se pot repeta în fișierul de intrare
* <code>1 ≤ k ≤ 100</code>
* lungimea fiecărui șir dat este mai mică decât <code>200</code>

= Exemplul 1: =
<code>veriflantIN.txt</code>
5 8
1 4
1 3
3 5
4 5
2 4
1 2
4 2
3 4
3
5 1 2 3 4 5
4 2 4 5 3
5 2 4 3 4 5
<code>veriflantOUT.txt</code>
NU
ELEMENTAR
NEELEMENTAR

= Exemplul 2: =
<code>veriflantIN.txt</code>
1001 100
1 4
1 3
3 5
4 5
2 4
1 2
4 2
3 4
3
5 1 2 3 4 5
4 2 4 5 3
5 2 4 3 4 5
<code>veriflantOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def citire_graf(muchii):
graf = {}
for i, j in muchii:
if i not in graf:
graf[i] = []
if j not in graf:
graf[j] = []
graf[i].append(j)
graf[j].append(i)
return graf

def este_lant(graf, sir):
for i in range(len(sir) - 1):
if sir[i + 1] not in graf[sir[i]]:
return False
return True

def este_elementar(sir):
return len(set(sir)) == len(sir)

def verifica_restrictii(n, muchii, k, vrf_siruri):
if not (1 <= n <= 100):
return False
for i, j in muchii:
if not (1 <= i <= n and 1 <= j <= n):
return False
if not (1 <= k <= 100):
return False
for sir in vrf_siruri:
if not (len(sir) < 200):
return False
return True

# Deschideți fișierele de intrare și ieșire
with open("veriflantIN.txt", "r") as input_file, open("veriflantOUT.txt", "w") as output_file:
n, m = map(int, input_file.readline().split())
muchii = [tuple(map(int, input_file.readline().split())) for _ in range(m)]

try:
k = int(input_file.readline())
except ValueError:
output_file.write("Datele nu corespund restrictiilor impuse\n")
exit()

vrf_siruri = [list(map(int, input_file.readline().split()[1:])) for _ in range(k)]

if verifica_restrictii(n, muchii, k, vrf_siruri):
graf = citire_graf(muchii)
for vrf_sir in vrf_siruri:
if este_lant(graf, vrf_sir):
if este_elementar(vrf_sir):
output_file.write("ELEMENTAR\n")
else:
output_file.write("NEELEMENTAR\n")
else:
output_file.write("NU\n")
else:
output_file.write("Datele nu corespund restrictiilor impuse\n")

</syntaxhighlight>

0474 - Verif Lant - Revision history