Участник:KislinskiyVadim/BLINNET

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/BLINNET/

parent = dict()
rank = dict()
 
def make_set(vertice):
    parent[vertice] = vertice
    rank[vertice] = 1
 
def find(vertice):
    if parent[vertice] != vertice:
        parent[vertice] = find(parent[vertice])
    return parent[vertice]
 
def union(vertice1, vertice2):
    root1 = find(vertice1)
    root2 = find(vertice2)
 
    if rank[root1] > rank[root2]:
        parent[root2] = root1
        rank[root1] += 1
        rank[root2] = 0
    else:
        parent[root1] = root2
        rank[root2] += 1
        rank[root1] = 0
 
def kruskal(n, edges):
    res = 0
    for vertice in range(n):
        parent[vertice] = vertice
        rank[vertice] = 0
 
    for edge in sorted(edges, key=lambda x: x[2]):
        vertice1, vertice2, weight = edge
        if find(vertice1) != find(vertice2):
            union(vertice1, vertice2)
            res += weight
 
    return res
 
for _ in range(int(input())):
    input()
    Ge = []
    n = int(input())  
    for x in range(n):
        input()
        m = int(input())   
        for y in range(m):
            nei, w = map(int, input().split())
            if nei > x:
                Ge.append((x, nei - 1, w))
    print (kruskal(n, Ge))