Simina: Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat. Să se determine numărul de muchii care pot fi eliminate din graf astfel încât numărul de componente conexe ale grafului să nu se modifice. = Date de intrare = Fişierul de intrare `componenteconexe2IN.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...

2023-12-13T10:56:35Z

Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat. Să se determine numărul de muchii care pot fi eliminate din graf astfel încât numărul de componente conexe ale grafului să nu se modifice. = Date de intrare = Fişierul de intrare <code>componenteconexe2IN.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...

New page

= Cerinţa =
Se dă lista muchiilor unui graf neorientat. Să se determine numărul de muchii care pot fi eliminate din graf astfel încât numărul de componente conexe ale grafului să nu se modifice.

= Date de intrare =
Fişierul de intrare <code>componenteconexe2IN.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>componenteconexe2OUT.txt</code> va conţine pe prima linie numărul <code>NR</code> de muchii care pot fi eliminate.

= 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>componenteconexe2IN.txt</code>
7
1 4
1 6
2 3
2 7
3 7
4 5
4 6
6 5
<code>componenteconexe2OUT.txt</code>
3

= Exemplul 2 =
<code>componenteconexe2IN.txt</code>
101
<code>componenteconexe2OUT.txt</code>
Datele nu corespund restrictiilor impuse
<syntaxhighlight lang="python3" line="1">
def verifica_restrictii(n, muchii):
if not (1 <= n <= 100):
return False
for muchie in muchii:
if not (1 <= muchie[0] <= n) or not (1 <= muchie[1] <= n):
return False
return True

def dfs(graful, vizitate, nod):
vizitate[nod] = True
for vecin in graful[nod]:
if not vizitate[vecin]:
dfs(graful, vizitate, vecin)

def numar_componente_conexe(graful, n):
vizitate = [False] * (n + 1)
numar = 0
for nod in range(1, n + 1):
if not vizitate[nod]:
numar += 1
dfs(graful, vizitate, nod)
return numar

def main():
with open("componenteconexe2IN.txt", "r") as f:
n = int(f.readline())
muchii = [tuple(map(int, linie.split())) for linie in f]

if not verifica_restrictii(n, muchii):
with open("componenteconexe2OUT.txt", "w") as f_out:
f_out.write("Datele nu corespund restrictiilor impuse")
return

graful = {i: [] for i in range(1, n + 1)}

for muchie in muchii:
graful[muchie[0]].append(muchie[1])
graful[muchie[1]].append(muchie[0])

numar_initial = numar_componente_conexe(graful, n)

numar_muchii_eliminate = 0

for muchie in muchii:
graful[muchie[0]].remove(muchie[1])
graful[muchie[1]].remove(muchie[0])

numar_final = numar_componente_conexe(graful, n)

if numar_final == numar_initial:
numar_muchii_eliminate += 1
else:
graful[muchie[0]].append(muchie[1])
graful[muchie[1]].append(muchie[0])

with open("componenteconexe2OUT.txt", "w") as f_out:
if numar_muchii_eliminate > 0:
f_out.write(str(numar_muchii_eliminate))
else:
f_out.write("Datele nu corespund restrictiilor impuse")

if __name__ == "__main__":
main()

</syntaxhighlight>

0537 - Componente Conexe 2 - Revision history