提出 #76523909

---

ソースコード 拡げる

class Union_find:
    def __init__(self, n) -> None:
        self.data = n
        self.parent = [-1] * n

    def union(self, u, v):
        u = self.root(u)
        v = self.root(v)
        if u == v:
            return
        if self.parent[u] < self.parent[v]:
            self.parent[u] += self.parent[v]
            self.parent[v] = u
        else:
            self.parent[v] += self.parent[u]
            self.parent[u] = v

    def find(self, u, v):
        if self.root(u) == self.root(v):
            return True
        else:
            return False

    def root(self, u):
        if self.parent[u] < 0:
            return u
        else:
            return self.root(self.parent[u])
    def group_sizes(self):
        res = []
        for p in self.parent:
            if p < 0:
                res.append(-p)
        return res

N, M = map(int, input().split())

cm = []
ks = []
for m in range(M):
    k,c = map(int, input().split())
    A = list(map(lambda x:int(x)-1, input().split()))
    cm.append((c,m))
    ks.append(A)

cm.sort()
dsu = Union_find(N)
ans = 0
for c, m in cm:
    for i in range(len(ks[m])-1):
        u = ks[m][i]
        v = ks[m][i+1]
        if not dsu.find(u,v):
            dsu.union(u,v)
            ans += c

if len(dsu.group_sizes()) == 1:
    print(ans)
else:
    print(-1)

提出情報

ジャッジ結果