0437 - Conex

Cerinţa

Se dă lista muchiilor unui graf neorientat. Să se verifice dacă graful este sau nu conex.

Date de intrare

Fişierul de intrare conexIN.txt conţine pe prima linie numărul n, reprezentând numărul de vârfuri ale grafului. Fiecare dintre următoarele linii conține câte o pereche de numere i j, cu semnificația că există muchie între i și j.

Date de ieşire

Fişierul de ieşire conexOUT.txt va conţine mesajul DA, dacă graful dat este conex, respectiv NU, în caz contrar.

Restricţii şi precizări

• 1 ≤ n ≤ 100
• 1 ≤ i , j ≤ n
• în fișierul de intrare muchiile se pot repeta

Exemplul 1

conexIN.txt

5
1 4 
3 5
2 4

conexOUT.txt

NU

Exemplul 2

conexIN.txt

101

conexOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

def respecta_restrictii(n, muchii):
    return 1 <= n <= 100 and all(1 <= i <= n and 1 <= j <= n for i, j in muchii)

def este_conex(n, muchii):
    # Verifică restricțiile
    if not respecta_restrictii(n, muchii):
        return "Datele nu corespund restrictiilor impuse"

    # Restul codului rămâne neschimbat

    lista_adiacenta = {i: set() for i in range(1, n + 1)}
    for muchie in muchii:
        x, y = muchie
        lista_adiacenta[x].add(y)
        lista_adiacenta[y].add(x)

    vizitat = set()

    def dfs(nod):
        vizitat.add(nod)
        for vecin in lista_adiacenta[nod]:
            if vecin not in vizitat:
                dfs(vecin)

    # Folosim DFS pentru a vizita toate nodurile din graf
    dfs(1)

    # Verificăm dacă toate nodurile au fost vizitate
    return "DA" if len(vizitat) == n else "NU"

# Citirea din fișierul de intrare
with open("conexIN.txt", "r") as fisier:
    n = int(fisier.readline())
    muchii = [tuple(map(int, linie.split())) for linie in fisier]

# Verifică restricțiile și scrie rezultatul în fișierul de ieșire
with open("conexOUT.txt", "w") as fisier:
    rezultat = este_conex(n, muchii)
    fisier.write(rezultat)