BVB Source Codes

Algorithm-Implementations Show UF.java Source code

Return Download Algorithm-Implementations: download UF.java Source code - Download Algorithm-Implementations Source code - Type:.java
  1.  
  2.  
  3.  
  4. public class UF {
  5.     private int[] id;     // id[i] = parent of i
  6.     private byte[] rank;  // rank[i] = rank of subtree rooted at i (cannot be more than 31)
  7.     private int count;    // number of components
  8.  
  9.     /**
  10.      * Initializes an empty union-find data structure with <tt>N</tt>
  11.      * isolated components <tt>0</tt> through <tt>N-1</tt>
  12.      * @throws java.lang.IllegalArgumentException if <tt>N &lt; 0</tt>
  13.      * @param N the number of sites
  14.      */
  15.     public UF(int N) {
  16.         if (N < 0) throw new IllegalArgumentException();
  17.         count = N;
  18.         id = new int[N];
  19.         rank = new byte[N];
  20.         for (int i = 0; i < N; i++) {
  21.             id[i] = i;
  22.             rank[i] = 0;
  23.         }
  24.     }
  25.  
  26.     /**
  27.      * Returns the component identifier for the component containing site <tt>p</tt>.
  28.      * @param p the integer representing one object
  29.      * @return the component identifier for the component containing site <tt>p</tt>
  30.      * @throws java.lang.IndexOutOfBoundsException unless <tt>0 &le; p &lt; N</tt>
  31.      */
  32.     public int find(int p) {
  33.         if (p < 0 || p >= id.length) throw new IndexOutOfBoundsException();
  34.         while (p != id[p]) {
  35.             id[p] = id[id[p]];    // path compression by halving
  36.             p = id[p];
  37.         }
  38.         return p;
  39.     }
  40.  
  41.     /**
  42.      * Returns the number of components.
  43.      * @return the number of components (between <tt>1</tt> and <tt>N</tt>)
  44.      */
  45.     public int count() {
  46.         return count;
  47.     }
  48.  
  49.     /**
  50.      * Are the two sites <tt>p</tt> and <tt>q</tt> in the same component?
  51.      * @param p the integer representing one site
  52.      * @param q the integer representing the other site
  53.      * @return true if the two sites <tt>p</tt> and <tt>q</tt> are in the same component; false otherwise
  54.      * @throws java.lang.IndexOutOfBoundsException unless
  55.      *      both <tt>0 &le; p &lt; N</tt> and <tt>0 &le; q &lt; N</tt>
  56.      */
  57.     public boolean connected(int p, int q) {
  58.         return find(p) == find(q);
  59.     }
  60.  
  61.  
  62.     /**
  63.      * Merges the component containing site <tt>p</tt> with the
  64.      * the component containing site <tt>q</tt>.
  65.      * @param p the integer representing one site
  66.      * @param q the integer representing the other site
  67.      * @throws java.lang.IndexOutOfBoundsException unless
  68.      *      both <tt>0 &le; p &lt; N</tt> and <tt>0 &le; q &lt; N</tt>
  69.      */
  70.     public void union(int p, int q) {
  71.         int i = find(p);
  72.         int j = find(q);
  73.         if (i == j) return;
  74.  
  75.         // make root of smaller rank point to root of larger rank
  76.         if      (rank[i] < rank[j]) id[i] = j;
  77.         else if (rank[i] > rank[j]) id[j] = i;
  78.         else {
  79.             id[j] = i;
  80.             rank[i]++;
  81.         }
  82.         count--;
  83.     }
  84.  
  85.  
  86. }
  87.  
downloadUF.java Source code - Download Algorithm-Implementations Source code
Related Source Codes/Software:
raty - 2017-04-22
RDVTabBarController - Highly customizable tabBar and tabBarController fo... 2017-04-22
material-icon-lib - Library containing over 1500 material vector icons... 2017-04-21
httpdiff - Perform the same request against two HTTP servers ... 2017-04-21
jquerytools - The missing UI library for the Web ... 2017-04-21
mcrouter - Mcrouter is a memcached protocol router for scalin... 2017-04-22
dynomite - A generic dynamo implementation for different k-v ... 2017-04-22
kityminder - Baidu brain figure 2017-04-22
llvm - Mirror of official llvm git repository located at ... 2017-04-22
RBBAnimation - Block-based animations made easy, comes with easin... 2017-04-22
ied - 2017-04-29
Nimble - A Matcher Framework for Swift and Objective-C 2017-04-29
MHVideoPhotoGallery - A Photo and Video Gallery 2017-04-29
shoulda-matchers - Collection of testing matchers extracted from Shou... 2017-04-29
Android-SlideExpandableListView - A better ExpandableListView, with animated expanda... 2017-04-29
AppSales-Mobile - App Sales allows iPhone and Mac App Store develope... 2017-04-29
react-templates - Light weight templates for react ... 2017-04-28
afterglow-theme - A minimal dark Theme for Sublime Text 2 and 3 2017-04-28
jwt-go - Golang implementation of JSON Web Tokens (JWT) 2017-04-28
DeerResume - Tool MarkDown online resume, online preview, edit,... 2017-04-28

 Back to top