Editing 3126 – Arbori in graf

= Cerința =
În judeţul lui Dorel sunt <code>n</code> localităţi legate între ele prin <code>m</code> drumuri. Dorel e interesat să afle în câte moduri se pot alege <code>n-1</code> drumuri din cele <code>m</code> date, astfel încât folosind aceste drumuri să se poată ajunge de la orice localitate la oricare alta.

= Date de intrare =
Fișierul de intrare <code>arbori_in_grafIN.txt</code> conține pe prima linie numerele <code>n</code> şi <code>m</code>, iar pe următoarele <code>m</code> linii câte o pereche de numere distincte de la <code>1</code> la <code>n</code>, reprezentând două localităţi între care există drum.

= Date de ieșire =
Fișierul de ieșire <code>arbori_in_grafOUT.txt</code> va conține pe prima linie numărul de moduri cerut, modulo <code>1.000.000.007</code>.

= Restricții și precizări =

* <code>2 ≤ n ≤ 50</code>
* <code>0 ≤ m ≤ n(n-1)/2</code>

== Exemplul 1 ==
arbori_in_grafIN.txt:

2 1

1 2

arbori_in_grafOUT.txt:

1

== Exemplul 2 ==
arbori_in_grafIN.txt:

99999999999 1

1 2

Output:

Invalid input! Please check the conditions: 2 ≤ n ≤ 50 and 0 ≤ m ≤ n(n-1)/2

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
MOD = 1000000007

def gcd(x, y, a, b):
    if b == 0:
        x, y = 1, 0
    else:
        gcd(x, y, b, a % b)
        aux = x
        x = y
        y = aux - y * (a // b)

def inverse(x):
    ins, inv = 0, 0
    gcd(inv, ins, x, MOD)
    if inv <= 0:
        inv = MOD + inv % MOD
    return inv

def determinant(a, n):
    semn = 1

    for i in range(1, n):
        if a[i][i] == 0:
            for j in range(i + 1, n + 1):
                if a[j][i] != 0:
                    a[i], a[j] = a[j], a[i]
                    semn *= -1
                    break

            if not a[i][i]:
                return 0

        for j in range(i + 1, n + 1):
            if a[i][i] < 0:
                a[i][i] += MOD
            p = (-a[j][i] * inverse(a[i][i])) % MOD
            if p < 0:
                p += MOD
            for k in range(i, n + 1):
                a[j][k] = (a[j][k] + p * a[i][k]) % MOD
                if a[j][k] < 0:
                    a[j][k] += MOD

    pp = 1
    for i in range(1, n + 1):
        pp = (pp % MOD * a[i][i] % MOD) % MOD
    return pp * semn

def validate_input(n, m):
    return 2 <= n <= 50 and 0 <= m <= n * (n - 1) // 2

def main():
    with open("arbori_in_grafIN.txt", "r") as f:
        n, m = map(int, f.readline().split())

        if not validate_input(n, m):
            print("Invalid input! Please check the conditions: 2 ≤ n ≤ 50 and 0 ≤ m ≤ n(n-1)/2")
            return

        a = [[0] * 51 for _ in range(51)]
        for _ in range(m):
            x, y = map(int, f.readline().split())
            a[x][y] = -1
            a[y][x] = -1
            a[x][x] += 1
            a[y][y] += 1

    det = determinant(a, n - 1)

    with open("arbori_in_grafOUT.txt", "w") as g:
        g.write(str(det))

if __name__ == "__main__":
    main()

</syntaxhighlight>