0437 - Conex - Revision history

Simina: Pagină nouă: = 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
2023-12-13T10:30:50Z

Pagină nouă: = 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 <code>conexIN.txt</code> conţine pe prima linie numărul <code>n</code>, reprezentând numărul de vârfuri ale grafului. Fiecare dintre următoarele 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>. = Date de ieşire = Fişierul de ieşire <c...

New page
= 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 <code>conexIN.txt</code> conţine pe prima linie numărul <code>n</code>, reprezentând numărul de vârfuri ale grafului. Fiecare dintre următoarele 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>.

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

= Restricţii şi precizări =

* <code>1 ≤ n ≤ 100</code>
* <code>1 ≤ i , j ≤ n</code>
* în fișierul de intrare muchiile se pot repeta

= Exemplul 1 =
<code>conexIN.txt</code>
5
1 4
3 5
2 4
<code>conexOUT.txt</code>
NU

= Exemplul 2 =
<code>conexIN.txt</code>
101
<code>conexOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
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)

</syntaxhighlight>