Editing 0963 - Bazine (section)

= Explicație =
Apa din bazinele <code>1</code>, <code>6</code>, <code>8</code> şi <code>10</code> comunică doar între acestea, fiind instalate ţevi. Astfel pentru aceste patru bazine este necesar să se deschidă un singur robinet pentru umplerea lor.

Apa din bazinele <code>4</code>, <code>5</code> şi <code>9</code> comunică, deoarece între acestea sunt ţevi. Astfel pentru aceste bazine este necesar să se deschidă un singur robinet.

Pentru bazinele <code>3</code> şi <code>7</code> între care există teavă, se deschide un singur robinet, cele două bazine nefiind legate prin ţevi de celelalte bazine

Bazinul <code>2</code> nu este cuplat cu niciun alt bazin, fiind necesar să se deschidă robinetul acestuia.

În total se deschid doar <code>4</code> robinete pentru a alimenta toate bazinele

== Exemplul 2 ==
<code>bazineIN.txt</code>
 5 5
<code>bazineOUT.txt</code>
 Datele nu corespund restrictiilor impuse
Rezolvare<syntaxhighlight lang="python3" line="1">
class Graf:
    def __init__(self, varfuri):
        self.varfuri = varfuri
        self.lista_adiacenta = {i: [] for i in range(1, varfuri + 1)}

    def adauga_muchie(self, u, v):
        self.lista_adiacenta[u].append(v)
        self.lista_adiacenta[v].append(u)

    def numar_minim_robinete(self):
        vizitate = set()
        robinete = 0

        for varf in range(1, self.varfuri + 1):
            if varf not in vizitate:
                robinete += 1
                self.dfs(varf, vizitate)

        return robinete

    def dfs(self, varf, vizitate):
        vizitate.add(varf)
        for vecin in self.lista_adiacenta[varf]:
            if vecin not in vizitate:
                self.dfs(vecin, vizitate)


def verifica_restrictii(n, m, perechi):
    if not(10 <= n <= 100) or not(8 <= m <= 400):
        return False

    for i in range(m):
        x, y = perechi[i]
        if not(1 <= x <= n) or not(1 <= y <= n) or x == y:
            return False

    for i in range(m):
        for j in range(i + 1, m):
            if set(perechi[i]) == set(perechi[j]):
                return False

    return True


if __name__ == "__main__":
    with open("bazineIN.txt", "r") as fisier_intrare:
        n, m = map(int, fisier_intrare.readline().split())
        perechi = [tuple(map(int, fisier_intrare.readline().split())) for _ in range(m)]

        if not verifica_restrictii(n, m, perechi):
            with open("bazineOUT.txt", "w") as fisier_iesire:
                fisier_iesire.write("Datele nu corespund restrictiilor impuse")
        else:
            graf = Graf(n)

            for x, y in perechi:
                graf.adauga_muchie(x, y)

            with open("bazineOUT.txt", "w") as fisier_iesire:
                k = graf.numar_minim_robinete()
                fisier_iesire.write(str(k))

</syntaxhighlight>