import java.util.*;

// Kruskal's Algorithm for Minimum Spanning Tree (MST)
class KruskalsAlgorithm {

    // Edge class to represent graph edges
    static class Edge implements Comparable {
        int src, dest, weight;
        Edge(int src, int dest, int weight) {
            this.src = src;
            this.dest = dest;
            this.weight = weight;
        }

        // Sort edges by weight (ascending)
        public int compareTo(Edge other) {
            return this.weight - other.weight;
        }
    }

    // Disjoint Set Union (Union-Find) with path compression + union by rank
    static class DSU {
        int[] parent;
        int[] rank;

        DSU(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i; // initially, each node is its own parent
                rank[i] = 0;
            }
        }

        // Find the root of a node (with path compression)
        int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]); // compress the path
            }
            return parent[x];
        }

        // Union two sets by rank (attach smaller tree under larger one)
        void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);

            if (rootX == rootY) return; // already in same set → ignore

            // attach smaller rank tree under the bigger one
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }

    public static int kruskalMST(int V, List edges) {
        // Step 1: Sort all edges by weight
        // ---------------------------------
        // Sorting takes O(E log E)
        Collections.sort(edges);

        DSU dsu = new DSU(V);
        int totalWeight = 0;
        int edgesUsed = 0;

        // Step 2: Iterate over edges in ascending order of weight
        // --------------------------------------------------------
        // Each union/find operation takes ~O(α(V)) ≈ constant time (amortized)
        for (Edge edge : edges) {
            int u = edge.src;
            int v = edge.dest;
            int w = edge.weight;

            // Step 3: Check if adding this edge forms a cycle
            int parentU = dsu.find(u);
            int parentV = dsu.find(v);

            if (parentU != parentV) {
                // Safe to add edge — no cycle
                dsu.union(u, v);
                totalWeight += w;
                edgesUsed++;

                // Optimization: stop once MST has (V - 1) edges
                if (edgesUsed == V - 1) break;
            }
        }

        return totalWeight;
    }

    public static void main(String[] args) {
        // Example Graph (Undirected):
        //     0
        //    / \
        //   1---2
        //   |  /|
        //   | / |
        //   3---4
        //
        // Edges with weights:
        // 0-1:10, 0-2:6, 0-3:5, 1-3:15, 2-3:4, 2-4:2, 3-4:7

        int V = 5;
        List edges = new ArrayList<>();

        edges.add(new Edge(0, 1, 10));
        edges.add(new Edge(0, 2, 6));
        edges.add(new Edge(0, 3, 5));
        edges.add(new Edge(1, 3, 15));
        edges.add(new Edge(2, 3, 4));
        edges.add(new Edge(2, 4, 2));
        edges.add(new Edge(3, 4, 7));

        int mstWeight = kruskalMST(V, edges);
        System.out.println("Total Weight of MST = " + mstWeight);
    }
}