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

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