Untitled

package main.MidtermPreparation.Tutorials.GreedyAlgorithms;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Scanner;

public class KruskalMST {
    /**
     * Optimizes the provided Phorest to be as close to an MST as possible.
     * @param n the number of nodes in the network
     * @param g all edges in the full graph
     * @param p the edges in the Phorest
     * @return total edge weight of optimized Phorest
     */
    public static String run(int n, Edge[] g, Edge[] p) {
        return new KruskalMST().solve(n, g, p);
    }

    public String solve(int nodes, Edge[] graph, Edge[] phorest) {

        int maxLoop = nodes - 1;
        int countLoop = 0;
        int total = 0;

        HashMap<Integer, Integer> set = new HashMap<Integer, Integer>();
        for(int i = 0; i < phorest.length; i++) {
            set.put(i, i);
        }

        
         for (int i = 0; i < phorest.length; i++) {
             if (!hasCycle(phorest[i].x, phorest[i].y, set)) {
                 countLoop++;
                 total += graph[i].l;
             }
         }

   Arrays.sort(graph);

        while(maxLoop != countLoop) {

            for(int i = 0; i < graph.length; i++) {
                if (!hasCycle(graph[i].x, graph[i].y, set)) {
                    countLoop++;
                    total += graph[i].l;
                }
            }
        }

        String ans = "" + total + "";

        return ans;

    }

    public static Edge[] makeGraph(Scanner sc) {
        int m = sc.nextInt();
        Edge[] edges = new Edge[m];

        for (int i = 0; i < m; i++) edges[i] = new Edge(sc.nextInt(), sc.nextInt(), sc.nextInt());

        Arrays.sort(edges, Comparator.comparingInt(e -> e.l));

        return edges;
    }


    public static boolean hasCycle(Integer source, Integer destination, HashMap<Integer, Integer> disjointSet) {
        int root = find(disjointSet, source);
        int root2 = find(disjointSet, destination);

        if (root == root2) return true;

        else union(disjointSet, source, destination);

        return false;
    }

    public static Integer find(HashMap<Integer, Integer> parent, Integer v) {
        // Vertex is the root
        if (parent.get(v) == v) return v;

        // recursive call
        return find(parent, parent.get(v));
    }

    public static void union(HashMap<Integer, Integer> parent, Integer start, Integer end) {
        Integer x = find(parent, start);
        Integer y = find(parent, end);

        parent.put(x, y);
    }
}