3126 – Arbori in graf

Cerința

În judeţul lui Dorel sunt n localităţi legate între ele prin m drumuri. Dorel e interesat să afle în câte moduri se pot alege n-1 drumuri din cele m 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 arbori_in_grafIN.txt conține pe prima linie numerele n şi m, iar pe următoarele m linii câte o pereche de numere distincte de la 1 la n, reprezentând două localităţi între care există drum.

Date de ieșire

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

Restricții și precizări

• 2 ≤ n ≤ 50
• 0 ≤ m ≤ n(n-1)/2

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

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