Add Structur Union-Find
authorDralagen <dralagen@dralagen.fr>
Wed, 13 Nov 2013 11:18:34 +0000 (12:18 +0100)
committerDralagen <dralagen@dralagen.fr>
Wed, 13 Nov 2013 11:18:34 +0000 (12:18 +0100)
src/ClasseUnion.java [new file with mode: 0644]

diff --git a/src/ClasseUnion.java b/src/ClasseUnion.java
new file mode 100644 (file)
index 0000000..16a23f2
--- /dev/null
@@ -0,0 +1,40 @@
+
+public class ClasseUnion {
+       private int[] p_;
+       
+       public ClasseUnion(int t){
+               p_ = new int[t];
+               for (int i = 0; i < t; i++) {
+                       p_[i] = -1;
+               }
+       }
+       
+       public int classe(int i) {
+               while (p_[i] != -1 ) {
+                       i = p_[i];
+               }
+               return i;
+       }
+       
+       public void union(int a, int b) {
+               int pa=0,pb=0;
+               while (p_[a] != -1) {
+                       pa++;
+                       a = p_[a];
+               }
+               
+               while (p_[b] != -1) {
+                       pb++;
+                       b = p_[b];
+               }
+               
+               if (a != b) {
+                       if (pa < pb) {
+                               p_[a] = b;
+                       }
+                       else {
+                               p_[b] = a;
+                       }
+               }
+       }
+}