Editing 3508 - Bal

== Cerinta ==

La balul din acest an participă n băieți și n fete, numerotați de la 1 la n. Compatibilitățile dintre aceștia pot fi reprezentate sub forma unui graf bipartit. Fie mat matricea de adiacentă. Atunci, băiatul i se poate cupla cu fata j doar dacă sunt compatibili, adică mat[i][j] = 1. Aflați numărul de moduri de a forma cele n cupluri.

== Date de intrare ==

Programul citește de la tastatură numărul n, iar apoi matricea de adiacență.

== Date de iesire ==

Programul va afișa pe ecran numărul de moduri de a forma cuplurile, modulo 1.000.000.007.

== Restrictii si precizari ==

*1 < n < 25

== Exemplul 1 ==
;Intrare
:3
:0 1 1
:1 0 1
:1 1 1
;Iesire
;Datele introduse corespund restrictiilor impuse
:3

== Exemplul 2 ==
;Intrare
:3
:-5 34 0
:3 87 0
:0 0 -1
;Iesire
;Datele introduse nu corespund restrictiilor impuse


== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def numara_cupluri(mat, n):
    MOD = 1000000007

    def dfs(baiat, vazut):
        vazut[baiat] = True
        for fata in range(n):
            if mat[baiat][fata] and not vazut[n + fata]:
                vazut[n + fata] = True

                if perechi[n + fata] == -1 or dfs(perechi[n + fata], vazut):
                    perechi[n + fata] = baiat
                    return True

        return False

    perechi = [-1] * (2 * n)
    rezultat = 0

    for baiat in range(n):
        vazut = [False] * (2 * n)
        if dfs(baiat, vazut):
            rezultat += 1

    return rezultat % MOD

# Citire număr de băieți/fete și matricea de adiacență
n = int(input("Introduceți numărul n: "))
matrice_adiacenta = [list(map(int, input().split())) for _ in range(n)]

# Calcul și afișare rezultat
rezultat = numara_cupluri(matrice_adiacenta, n)
print(rezultat)
</syntaxhighlight>

== Explicatie ==

Cele 3 modalități sunt:
:(1, 2), (2, 1), (3, 3)
:(1, 2), (2, 3), (3, 1)
:(1, 3), (2, 1), (3, 2)