Editing 0474 - Verif Lant

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