package test.graph;
// kruskal

import java.util.*;

public class Kruskal {

  // edges: [cost,from,to]

  public static int[][] mstKruskal(int[][] edges, int n) {

    UnionFind uf = new UnionFind(n);

    Arrays.sort(edges, new Comparator<int[]>() {
      public int compare(int[] e1, int[] e2) {
	if (e1[0] < e2[0]) return -1;
	if (e1[0] > e2[0]) return 1;
	return 0;
      }});

    int[][] mst = new int[n-1][];
    int offset = 0;

    for(int[] edge: edges) {

      int root1 = uf.find(edge[1]);
      int root2 = uf.find(edge[2]);

      if (root1 != root2) {
	mst[offset++] = edge;
	if (offset == n-1) {
	  break;
	}
	uf.union(root1,root2);
      }
    }
    return mst;
  }

  public static void main(String[] args) {

    int[][] graph = new int[][]{ new int[]{100,0,1}, 
				 new int[]{200,1,2},
				 new int[]{300,2,3},
				 new int[]{400,3,1},
				 new int[]{500,0,2}
    }; 
				 

    System.out.println("graph = " + Arrays.deepToString(graph));

    int[][] mst = mstKruskal(graph,4);

    System.out.println("mst = " + Arrays.deepToString(mst));

  }

}