daily pastebin goal
96%
SHARE
TWEET

Untitled

a guest Mar 22nd, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.Scanner;
  2.  
  3. public class DSmove {
  4.     private Node[] nodes;
  5.  
  6.     public DSmove(int n) {
  7.         this.nodes = new Node[n];
  8.  
  9.         for (int i=0; i < n; i++) {
  10.             nodes[i] = new Node(i);
  11.         }
  12.     }
  13.  
  14.     public Node find(int x) {
  15.         Node node = nodes[x];
  16.         while (node.id != node.parent.id)
  17.             node = node.parent;
  18.         return node;
  19.     }
  20.  
  21.     public void union(int p, int q) {
  22.         Node rootP = find(p);
  23.         Node rootQ = find(q);
  24.  
  25.         if (rootP.id == rootQ.id) return;
  26.  
  27.         if (rootP.size > rootQ.size) {
  28.             //Move rootQ to be a child of rootP
  29.            
  30.             //Start by increasing the size of the immediateChildren array (if necessary)
  31.             if (rootP.numberOfImmediateChildren == rootP.immediateChildren.length) {
  32.                 increaseArraySize(n);
  33.             }
  34.  
  35.             //Add rootQ as an immediate child of rootP
  36.             rootP.immediateChildren[rootP.numberOfImmediateChildren] = rootQ;
  37.             //Increate the number of immediate children that rootP has
  38.             rootP.numberOfImmediateChildren++;
  39.             //Increase the total size of rootP
  40.             rootP.size += rootQ.size;
  41.  
  42.             //Mark rootQ as largest child of rootP if that is indeed the case
  43.             if (rootQ.size > rootP.largestChild.size) {
  44.                 rootP.largestChild = rootQ;
  45.             }
  46.         } else {
  47.             //DIY
  48.         }
  49.     }
  50.  
  51.     private void increaseArraySize(Node n) {
  52.         //Do the smart size increase (check your books)
  53.         Node[] newArray = new Node[n.immediateChildren.length * 2];
  54.  
  55.         for (int i = 0; i < n.numberOfImmediateChildren; i++) {
  56.             newArray[i] = n.immediateChildren[i];
  57.         }
  58.  
  59.         n.immediateChildren = newArray;
  60.     }
  61.  
  62.     private class Node {
  63.         private int id;
  64.         private int size;
  65.         private int numberOfImmediateChildren;
  66.  
  67.         private Node parent = this;
  68.         private Node[] immediateChildren = new Node[1];
  69.         private Node largestChild = null;
  70.  
  71.         Node(int i) {
  72.             this.id = i;
  73.             this.size = 1;
  74.             this.numberOfImmediateChildren = 0;
  75.         }
  76.     }
  77. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top