S4CTF 2021 | pts

#s4ctf_2021

隣接行列によって無向非巡回グラフが与えられるから、全域木の個数を返せ、という問題

全域木の個数はラプラシアン行列の余因子で与えられる

from ptrlib import Socket
import ast

sock = Socket("198.211.127.76", 3580)
while True:
    sock.recvuntil("M =\n")
    M = ast.literal_eval(sock.recvuntil("|")[:-1].decode().replace("\n", ","))
    M = matrix(M)
    G = Graph(M)
    L = G.kirchhoff_matrix()
    ans = L.adjugate()[0,0]

    print(M)
    print(ans)
    sock.sendlineafter("please send number of subtrees\n", str(ans))
    print(sock.recvline())
    input("Hit Enter to next")