title: What is wrong with my implementation of Kruskal's algorithm using union-find data structure.
body: <p>I am trying to implement the Kruskal's algorithm, and find the sum of the weights in the MST.
  I think my problem lays somewhere where I set the parent of each node, but I am not sure, because in small examples it works fine, however with big example it doesnt detect a cycle, and the final answer is wrong. so my find might be wrong, but I am not sure.
  Here is my code:</p>
  
  <pre><code>import java.io.File;
  import java.io.FileNotFoundException;
  import java.util.ArrayList;
  import java.util.Collections;
  import java.util.HashMap;
  import java.util.Iterator;
  import java.util.LinkedHashMap;
  import java.util.List;
  import java.util.Scanner;
  
  public class Graph {
      private static int parent[];
      private static int numberOfNodes, numberOfEdges, weight;
      private static Node startNode, endNode;
      private static Graph g;
      private static ArrayList&lt;Integer&gt; listOfWeights = new ArrayList&lt;Integer&gt;();
      private static ArrayList&lt;Edge&gt; listOfEdges = new ArrayList&lt;Edge&gt;();
      private static ArrayList&lt;Node&gt; listOfNodes = new ArrayList&lt;Node&gt;();
      private static HashMap&lt;Edge, Integer&gt; distance = new HashMap&lt;Edge, Integer&gt;();
      private static HashMap&lt;Edge, Integer&gt; sortedMap = new HashMap&lt;Edge, Integer&gt;();
      //values = Integer
      private Scanner sc;
  
      public static void main(String[] args) throws FileNotFoundException {
          // TODO Auto-generated method stub
          g = new Graph();
      }
  
      public Graph() throws FileNotFoundException {
  
          sc = new Scanner(new File("data"));
          numberOfNodes = Integer.parseInt(sc.next());
          numberOfEdges = Integer.parseInt(sc.next());
  
          if(numberOfEdges &gt; 0){
              for(int i = 0; i &lt; numberOfEdges; i++) {
                  //read the start point
                  startNode = new Node(Integer.parseInt(sc.next()));
                  //read the end point
                  endNode = new Node(Integer.parseInt(sc.next()));
                  //read the price per node
                  weight = Integer.parseInt(sc.next());
                  Edge e = new Edge(startNode,endNode);
                  //set the weight per node
                  e.setWeight(weight);
                  //put them in a hashmap
                  distance.put(e,e.getWeight());
                  if(!listOfNodes.contains(startNode)){
                      listOfNodes.add(startNode);
                  }
                  if(!listOfNodes.contains(endNode)){
                      listOfNodes.add(endNode);
                  }
                  //System.out.println(distance.get(e));
              }
              System.out.println("without sort distance: " + distance.toString());
              for (Object key : distance.keySet()) {
                  listOfEdges.add((Edge) key);
              }
              for (Object value : distance.values()) {
                  listOfWeights.add((Integer) value);
              }
              sortedMap = sortHashMapByValuesD(distance);
              //System.out.println("list of nodes: "+ listOfNodes);
              parent = new int[listOfNodes.size()];
              System.out.println("sorted by weights: "+sortedMap.toString());
              System.out.println(kruskalAlgo(sortedMap));
          }
          else{
              System.out.println(0);
          }
      }
  
      public static void makeSet(int x){
          parent[x-1] = x;
      }
  
      public static int find(int x){
          //System.out.println("FIND ==&gt; x: " + x + ".parent = " + parent[x-1] );
          if(parent[x-1] == x){
              return x;
          }
          return find(parent[x-1]);
      }
  
      public static void union(int x, int y){
          //System.out.println("parent[0]: "+parent[0]);
          parent[x-1] = y;
          System.out.println("x: " + x + " UNION parent[x-1]: " + parent[x-1] + " y " + y );
      }
  
      public static int kruskalAlgo(HashMap&lt;Edge, Integer&gt; s){
          parent[0] = 0;
          for(int i = 0; i &lt; parent.length; i++){
              makeSet(listOfNodes.get(i).getId());
              //System.out.println("parent is: "+parent[i] + " for node"+ listOfNodes.get(i));
          }
          // for each edge (u,v) ∈ G, taken in increasing order by weight
          int min = 0;
          int edgeNumber = 0;
          for (Edge key : s.keySet()) {
              if(edgeNumber == listOfNodes.size()-1){
                  //System.out.println("edgeNumber: "+ edgeNumber);
                  //System.out.println("listOfNodes.size()-1: "+ (listOfNodes.size()-1));
                  return min;
              }
              Node u = key.getFromNode();
              //System.out.println(u);
              Node v = key.getToNode();
              //System.out.println(v);
              if(find(u.getId()) != find (v.getId())){
                  min += key.getWeight();
                  union(u.getId(),v.getId());
                  System.out.println(key + " weight is: " + key.getWeight());
                  edgeNumber++;
              }
          }
          return min;
      }
  
      public static ArrayList&lt;Edge&gt; findSet(Node v){
          ArrayList&lt;Edge&gt; nodes = new ArrayList&lt;Edge&gt;();
          return nodes;
      }
  
      //make an ordered listed by increasing weights
      public LinkedHashMap&lt;Edge, Integer&gt; sortHashMapByValuesD(HashMap&lt;Edge, Integer&gt; newMap) {
          //list of edges    
          List&lt;Edge&gt; mapKeys = new ArrayList&lt;Edge&gt;(newMap.keySet());
          //list of nodes
          List&lt;Integer&gt; mapValues = new ArrayList&lt;Integer&gt;(newMap.values());
          //sort the nodes
          Collections.sort(mapValues);
          LinkedHashMap&lt;Edge, Integer&gt; sortedMap = new LinkedHashMap&lt;Edge, Integer&gt;();
          Iterator&lt;Integer&gt; valueIt = mapValues.iterator();
          while (valueIt.hasNext()) {
              Object val = valueIt.next();
              Iterator&lt;Edge&gt; keyIt = mapKeys.iterator();
              while (keyIt.hasNext()) {
                  Object key = keyIt.next();
                  String comp1 = newMap.get(key).toString();
                  String comp2 = val.toString();
  
                  if (comp1.equals(comp2)){
                      newMap.remove(key);
                      mapKeys.remove(key);
                      sortedMap.put((Edge)key, (Integer)val);
                      break;
                 }
             }
          }
          return sortedMap;
      }
  }
  </code></pre>