Questões do URI.

Lista7.py

# Itinerário do Papai Noel

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in xrange(n)]

    def find(self, elem):
        if self.parent[elem] != elem:
            self.parent[elem] = self.find(self.parent[elem])
        return self.parent[elem]

    def union(self, elem1, elem2):
        p1 = self.find(elem1)
        p2 = self.find(elem2)
        if p1 != p2:
            self.parent[p2] = p1

    def connected(self, elem1, elem2):
        return self.find(elem1) == self.find(elem2)

while True:
    m, n = map(int, raw_input().split())
    if m == n == 0:
        break
    
    edges = []
    for i in xrange(n):
        cid1, cid2, dist = map(int, raw_input().split())
        edges.append((cid1, cid2, dist))
    edges = sorted(edges, key=lambda e: e[2], reverse=True)
    
    uf = UnionFind(m)
    total = 0

    while edges:
        cid1, cid2, dist = edges.pop()
        if not uf.connected(cid1, cid2):
            uf.union(cid1, cid2)
            total += dist

    print total
    
# Estradas Escuras

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in xrange(n)]

    def find(self, elem):
        if self.parent[elem] != elem:
            self.parent[elem] = self.find(self.parent[elem])
        return self.parent[elem]

    def union(self, elem1, elem2):
        p1 = self.find(elem1)
        p2 = self.find(elem2)
        if p1 != p2:
            self.parent[p2] = p1

    def connected(self, elem1, elem2):
        return self.find(elem1) == self.find(elem2)

while True:
    m, n = map(int, raw_input().split())
    if m == n == 0:
        break
    
    edges = []
    for i in xrange(n):
        cid1, cid2, dist = map(int, raw_input().split())
        edges.append((cid1, cid2, dist))
    edges = sorted(edges, key=lambda e: e[2], reverse=True)
    
    uf = UnionFind(m)
    saved = 0

    while edges:
        cid1, cid2, dist = edges.pop()
        if not uf.connected(cid1, cid2):
            uf.union(cid1, cid2)
        else:
            saved += dist

    print saved
    
# Copa do Mundo

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in xrange(n)]

    def find(self, elem):
        if self.parent[elem] != elem:
            self.parent[elem] = self.find(self.parent[elem])
        return self.parent[elem]

    def union(self, elem1, elem2):
        p1 = self.find(elem1)
        p2 = self.find(elem2)
        if p1 != p2:
            self.parent[p2] = p1

    def connected(self, elem1, elem2):
        return self.find(elem1) == self.find(elem2)

n, f, r = map(int, raw_input().split())

ferrovias = []
for i in xrange(f):
    cid1, cid2, dist = map(int, raw_input().split())
    ferrovias.append((cid1 - 1, cid2 - 1, dist))

rodovias = []
for i in xrange(r):
    cid1, cid2, dist = map(int, raw_input().split())
    rodovias.append((cid1 - 1, cid2 - 1, dist))

ferrovias = sorted(ferrovias, key=lambda e: e[2], reverse=True)
rodovias = sorted(rodovias, key=lambda e: e[2], reverse=True)

uf = UnionFind(n)
custo = 0

while ferrovias:
    cid1, cid2, dist = ferrovias.pop()
    if not uf.connected(cid1, cid2):
        uf.union(cid1, cid2)
        custo += dist

while rodovias:
    cid1, cid2, dist = rodovias.pop()
    if not uf.connected(cid1, cid2):
        uf.union(cid1, cid2)
        custo += dist
        
print custo

# Reduzindo Detalhes em um Mapa
class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in xrange(n)]

    def find(self, elem):
        if self.parent[elem] != elem:
            self.parent[elem] = self.find(self.parent[elem])
        return self.parent[elem]

    def union(self, elem1, elem2):
        p1 = self.find(elem1)
        p2 = self.find(elem2)
        if p1 != p2:
            self.parent[p2] = p1

    def connected(self, elem1, elem2):
        return self.find(elem1) == self.find(elem2)

n, m = map(int, raw_input().split())

edges = []
for i in xrange(m):
    cid1, cid2, dist = map(int, raw_input().split())
    edges.append((cid1 - 1, cid2 - 1, dist))

edges = sorted(edges, key=lambda e: e[2], reverse=True)

uf = UnionFind(n)
total = 0

while edges:
    cid1, cid2, dist = edges.pop()
    if not uf.connected(cid1, cid2):
        uf.union(cid1, cid2)
        total += dist
        
print total