package com.data.struct;

import java.util.ArrayList;
import java.util.List;

public class DisJoinSet {
  private List<Node> set;
  public DisJoinSet(int []ids){
    set=new ArrayList<Node>();
    Node n=null;
    for(int i=0;i<ids.length;i++){
      Node node=new Node();
      node.id=ids[i];
      makeSet(node);
      set.add(node);
      if(n==null){
        n=node;
      }else{
        union(n,node);
      }
      
    }
  }
  public void makeSet(Node x){
    x.parent=x;
    x.rank=0;
  }
  public void union(Node x,Node y){
     link(findSet(x),findSet(y));
  }
  private void link(Node x,Node y){
    if(x.rank>y.rank){
      y.parent=x;
    }else{
      x.parent=y;
      if(x.rank==y.rank){
        y.rank++;
      }
    }
    
  }
  public Node findSet(Node x){
    if(x.parent!=x){
      x.parent=findSet(x.parent);
    }
    return x.parent;
  }
  public void print(){
    for(int i=0;i<set.size();i++){
      Node node=set.get(i);
      while(node.parent!=node){
        System.out.print(node.id+" ");
        node=node.parent;
      }
      System.out.print(node.id+" ");
      System.out.println();
    }
  }
  private class Node{
    private int rank;
    private Node parent;
    private int id;
  }
  public static void main(String[] args) {
    int []ids=new int[]{1,2,3,4,5,6,7,8,9};
    DisJoinSet set=new DisJoinSet(ids);
    set.print();
    

  }

}