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

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