0474 - Verif Lant

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

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

Date de ieşire

Fişierul de ieşire veriflantOUT.txt va conține k linii. Fiecare linie va contine unul dintre cuvintele NU, ELEMENTAR, NEELEMENTAR, 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

• 1 ≤ n ≤ 100
• 1 ≤ i , j ≤ n
• muchiile se pot repeta în fișierul de intrare
• 1 ≤ k ≤ 100
• lungimea fiecărui șir dat este mai mică decât 200

Exemplul 1:

veriflantIN.txt

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

veriflantOUT.txt

NU
ELEMENTAR
NEELEMENTAR

Exemplul 2:

veriflantIN.txt

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

veriflantOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

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