0537 - Componente Conexe 2

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ția că există muchie între i și j.

Date de ieşire

Fişierul de ieşire componenteconexe2OUT.txt va conţine pe prima linie numărul NR de muchii care pot fi eliminate.

Restricţii şi precizări

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

Exemplul 1

componenteconexe2IN.txt

7
1 4
1 6
2 3
2 7
3 7
4 5
4 6
6 5

componenteconexe2OUT.txt

3

Exemplul 2

componenteconexe2IN.txt

101

componenteconexe2OUT.txt

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>