BOJ. MST (Minimum Spanning Tree) (1197)

Problem · 한국어 · 日本語

Kruskal’s algorithm

A spanning tree connects every vertex without cycles. A minimum spanning tree (MST) is a spanning tree with the smallest possible total edge weight. Kruskal’s algorithm sorts edges in nondecreasing weight order and accepts an edge exactly when its endpoints are in different components. A disjoint-set union (DSU) structure detects that condition and merges the components.

The greedy choice is safe: among the edges joining distinct current components, the lightest can be included in some MST (the cut property). Repeating this choice builds a forest without cycles; once it has V - 1 edges, it is a spanning tree and therefore an MST. Edge weights may be negative: sorting and the cut-property argument still apply, and negative edges should be included whenever they connect separate components.

The endpoints are treated symmetrically. Keep both original endpoint values when reading an edge; there is no need to reorder them for Kruskal. Compare weights with Integer.compare rather than subtraction, which can overflow. The total is stored in long, since adding as many as V - 1 int-weight edges may exceed the int range. With E edges and V vertices, sorting dominates at O(E log E) time; DSU operations take amortized O(α(V)) each. Space usage is O(V + E).

import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Main {
    public static void main(String[] args) throws IOException {
        FastScanner input = new FastScanner();
        int vertexCount = input.nextInt();
        int edgeCount = input.nextInt();
        List<Edge> edges = new ArrayList<>(edgeCount);

        for (int i = 0; i < edgeCount; i++) {
            int a = input.nextInt() - 1;
            int b = input.nextInt() - 1;
            int weight = input.nextInt();
            edges.add(new Edge(a, b, weight));
        }

        edges.sort(Comparator.comparingInt(edge -> edge.weight));
        DisjointSet sets = new DisjointSet(vertexCount);
        long totalWeight = 0;
        int acceptedEdges = 0;

        for (Edge edge : edges) {
            if (!sets.union(edge.a, edge.b)) {
                continue;
            }
            totalWeight += edge.weight;
            acceptedEdges++;
            if (acceptedEdges == vertexCount - 1) {
                break;
            }
        }

        System.out.println(totalWeight);
    }

    private static final class Edge {
        final int a;
        final int b;
        final int weight;

        Edge(int a, int b, int weight) {
            this.a = a;
            this.b = b;
            this.weight = weight;
        }
    }

    private static final class DisjointSet {
        private final int[] parent;
        private final int[] size;

        DisjointSet(int n) {
            parent = new int[n];
            size = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        private int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        boolean union(int a, int b) {
            int rootA = find(a);
            int rootB = find(b);
            if (rootA == rootB) {
                return false;
            }
            if (size[rootA] < size[rootB]) {
                int temp = rootA;
                rootA = rootB;
                rootB = temp;
            }
            parent[rootB] = rootA;
            size[rootA] += size[rootB];
            return true;
        }
    }

    private static final class FastScanner {
        private final BufferedInputStream input = new BufferedInputStream(System.in);
        private final byte[] buffer = new byte[1 << 16];
        private int length;
        private int position;

        private int read() throws IOException {
            if (position == length) {
                length = input.read(buffer);
                position = 0;
                if (length == -1) {
                    return -1;
                }
            }
            return buffer[position++];
        }

        int nextInt() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);
            int sign = 1;
            if (c == '-') {
                sign = -1;
                c = read();
            }
            int value = 0;
            while (c > ' ') {
                value = value * 10 + c - '0';
                c = read();
            }
            return sign * value;
        }
    }
}