• API
• FAQ
• Tools
• Archive
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.

Top