Corjuc Eunice: Pagină nouă: = 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 u...

2024-01-03T21:10:14Z

Pagină nouă: = 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 u...

New page

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

3126 – Arbori in graf - Revision history