Untitled

unknown
java
a year ago
2.5 kB
1
Indexable
Never
```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
*/
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);
}

while (maxLoop != countLoop) {

for (int i = 0; i < phorest.length; i++) {

if (!hasCycle(phorest[i].x, phorest[i].y, set)) {
countLoop++;
}
}
}

while(maxLoop != countLoop) {

for(int i = 0; i < phorest.length; i++) {

total += find(set, phorest[i].x);

}
}

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);
}
}
```