/**
 * Kruskal's algorithm
 * @param graph graph
 * @param w weight vector of the edges
 * @return minimum spanning tree
 */
SpanningTree kruskalAlgorithm(Graph graph, weights w)
    SpanningTree tree 
    for Node n : graph do
        makeSet(n) //every edge is considered as a separate component
    List edges = sort(graph.getEdges(), w) //order the edges according to their weight in ascending order
    
    for Edge e in edges do
        if findSet(e.start) != findSet(e.end) //if the source and target are in different components, than we are not creating a cycle
            tree.add(e) //add the edge to the spanning tree
            union(e.start, e.end) //merge the connected components
            if tree.edgeCount() == graph.nodeCount() - 1 //if the spanning tree is complete
                break //terminate the algorithm
    return tree

/**
 * Kruskal's algorithm
 * @author Pavel Micka
 */
public class KruskalAlgorithm {
    /**
     * Finds the minimum spanning tree of the given grapg with n vertices (the vertices are numbered
     * 0, 1, ..., n-1)
     * @param edges edges of the undirected graph
     * @param nodeCount number of vertices (n)
     * @return minimum spanning tree
     */
    public static List<Edge> kruskalAlgorithm(List<Edge> edges, int nodeCount) {
        DisjointSet ds = new DisjointSet(nodeCount);
        List<Edge> spanningTree = new ArrayList<Edge>();
        Collections.sort(edges);
        int i = 0;
        while (i != edges.size() && spanningTree.size() != nodeCount - 1) {
            Edge e = edges.get(i);
            if(ds.find(e.getFrom()) != ds.find(e.getTo())){
                spanningTree.add(e);
                ds.union(e.getFrom(), e.getTo());
            }
            i++;
        }
        return spanningTree;
    }
}


// ***************************** //
// *      Data Structures      * //
// ***************************** //


/**
 * Edge of a undirected graph
 * @author Pavel Micka
 */
class Edge implements Comparable<Edge> {
    private int from; //from
    private int to; //to
    private int weight; //weight
    public Edge(int from, int to, int weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }
    /**
     * Compare to function (greater weight => is greater than)
     * @param o
     * @return
     */
    public int compareTo(Edge o) {
        if (this.getWeight() > o.getWeight()) {
            return 1;
        } else if (this.getWeight() < o.getWeight()) {
            return -1;
        } else {
            return 0;
        }
    }

    /**
     * @return the from
     */
    public int getFrom() {
        return from;
    }

    /**
     * @param from the from to set
     */
    public void setFrom(int from) {
        this.from = from;
    }

    /**
     * @return the to
     */
    public int getTo() {
        return to;
    }

    /**
     * @param to the to to set
     */
    public void setTo(int to) {
        this.to = to;
    }

    /**
     * @return the weight
     */
    public int getWeight() {
        return weight;
    }

    /**
     * @param weight the weight to set
     */
    public void setWeight(int weight) {
        this.weight = weight;
    }
}
/**
 * Implementation of the disjoint set structure
 * @author Pavel Micka
 */
class DisjointSet {

    private Node[] nodes;

    public DisjointSet(int nodeCount) {
        nodes = new Node[nodeCount];
        for (int i = 0; i < nodeCount; i++) {
            nodes[i] = new Node();
            nodes[i].id = i;
        }
    }

    /**
     * Unions sets, which contain vertices "a" and "b"
     * Union is always performed as merging "B" into "A"
     * @param a number of a node "a"
     * @param b number of a node "b"
     * @return number of a representative of the merged component
     */
    public int union(int a, int b) {
        Node repA = nodes[find(a)];
        Node repB = nodes[find(b)];

        repB.parent = repA;
        return repA.id;
    }

    /**
     * Returns representative of the compoment which contains the given node
     * @param a number of a node, whose representative we are looking for
     * @return number of the representative
     */
    public int find(int a) {
        Node n = nodes[a];
        int jumps = 0;
        while (n.parent != null) {
            n = n.parent;
            jumps++;
        }
        if (jumps > 1) repair(a, n.id);
        return n.id;
    }

    /**
     * Performs compression of the path
     * @param a
     * @param rootId
     */
    private void repair(int a, int rootId) {
        Node curr = nodes[a];
        while (curr.id != rootId) {
            Node tmp = curr.parent;
            curr.parent = nodes[rootId];
            curr = tmp;
        }
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < nodes.length; i++) {
            builder.append(find(i) + " ");
        }
        return builder.toString();
    }

    /**
     * Vertex of an n-ary tree
     */
    private static class Node {
        /**
         * Parent
         */
        Node parent;
        /**
         * Node id
         */
        int id;
    }
}