Editorial for MST

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

Sort the edges by increasing weight and run Kruskal's algorithm with a DSU.

For each edge in sorted order, add it to the forest if its endpoints lie in different components. The sum of added edge weights is the MST weight. If fewer than $n - 1$ ~n - 1~ edges are added, the graph is disconnected and the answer is -1.

With union by size and path compression this is nearly $O(m \log m)$ ~O(m \log m)~.

Solution (Python)

class DisjointSet:
    def __init__(self, size: int) -> None:
        self.parent = list(range(size))
        self.size = [1] * size

    def find_set(self, v: int) -> int:
        if self.parent[v] == v:
            return v
        self.parent[v] = self.find_set(self.parent[v])
        return self.parent[v]

    def union(self, v: int, u: int) -> bool:
        a = self.find_set(v)
        b = self.find_set(u)
        if a == b:
            return False
        if self.size[a] > self.size[b]:
            a, b = b, a
        self.parent[a] = b
        self.size[b] += self.size[a]
        return True


n, m = (int(x) for x in input().split())
edges = []
for _ in range(m):
    a, b, c = (int(x) for x in input().split())
    edges.append((c, a, b))

edges.sort()
dsu = DisjointSet(n + 1)
total = 0
taken = 0
for c, a, b in edges:
    if dsu.union(a, b):
        total += c
        taken += 1

print(total if taken == n - 1 else -1)

Comments

There are no comments at the moment.