全域木を列挙してみた

引数
n:ノードの数
lst:[(u1,v1),(u2,v2),...]こんな感じ

unionfindはこれを使ってます
https://note.nkmk.me/python-union-find/

使用例
zenikigi(5,[(0,1),(0,2),(1,2),(1,3),(1,4)])
ー＞[(0, 1, 3, 4), (0, 2, 3, 4), (1, 2, 3, 4)]

from copy import deepcopy
def zenikigi(n,lst):
    re=set()
    ans=[]
    re.add((tuple(),UnionFind(n)))
    for i in range(len(lst)):
        tmp=set()
        for v in re:
            t,uni=v
            if not uni.same(*lst[i]):
                if len(t)==n-2:
                    ans.append(t+tuple([i]))
                uni2=deepcopy(uni)
                uni2.union(*lst[i])
                tmp.add((t+tuple([i]),uni2))

        re|=tmp
    return ans