Question

Hi. Are you familiar with deunions? The objective of the task is to undo the last union operation in a weighted quick-union find implementation, of which I have partly written here (see below). I push the unions on a stack. The code is not finished though, and far from perfect. Can you point out my mistakes and figure out how to create the deunion-operation correctly?

Best regards,

Eirik

public class UFwithDeunion {

    private int[] id; //parent link (site indexed)
    private int[] sz; // size of component for roots (site indexed)
    private int count; //number of components
    Stack stack = new Stack();

    //maa bruke weighted-quick union for at det skal kjoere i ¨log N kjoeretid

    public UFwithDeunion(int n) {
        count = n;
        id = new int[n];
        for (int i = 0; i < n; i++)
            id[i] = i;
    }

    //set the total number of elements
    public static int setSize(int n){
        sz = new int[n];
        for (int i = 0; i < n; i++)
            sz[i] = 1;
    }

    //return an identifier for the set containing a
    public static int find(int a){ //follow links to find a root
        while (a != id[a])
            a = id[a]; //pop
        return a;


    //merge the set containing a with the set containing b
    public static void union(int a, int b){

        int i = find(a);
        int j = find(b);
        if (i == j) return;
        //make smaller root point to larger one
        if (sz[i] < sz[j]) {
            id[i] = j; sz[j] += sz[i];
            stack.push(id[i]);
        }
        else {
            id[j] = i; sz[i] += sz[j];
            stack.push(id[j]);
        }
    }

    // undo the last union operation
    public static void deUnion(){
        stack.pop();
        //sz--;
    }

    //Return the number of elements in the set containing a
    public static int elementsInSet(int a){
        int sum = 0;
        for (int i : id) {
            if (a == id[i])
                sum++;
        }
        return sum;
    }

Answer 1

The idea to solve this question is maintain a stack of user created class that stores the information of groups before the union
operation and push it onto the stack and when we need to do deunion operation, we pop this object and use its information to reset the group information to the state it was before the union operation. I have mentioned outside each function to the changes I made and new statements have explanation along with them. I have demo run this code with 10 elements and I have used find operation on each element before and after the deunion operation to show the difference and show the deunion was succesful and a screenshot has been attached. If you face any problem, let me know in the comments.

Code:

import java.util.*;
class UnionInfo //Created a new Class for storing info about the union operations we are doing
{
int l1, l2; //l1 and l2 are leaders of the two groups on which we applied union operation
int size1, size2;// We will store the size of both groups before the union operation
}
class UFwithDeunion { //Changed static methods into non static, private to public for easy access

int[] id; //parent link (site indexed)
int[] sz; // size of component for roots (site indexed)
int count; //number of components
Stack<UnionInfo> stack = new Stack<UnionInfo>(); //Created a stack with UnionInfo objects which store
//all information about union operations done

//maa bruke weighted-quick union for at det skal kjoere i ¨log N kjoeretid

public UFwithDeunion(int n) {//Called setSize function in the constructor itself,other things are same
count = n;
id = new int[n];
for (int i = 0; i < n; i++)
id[i] = i;
setSize(n);
}

//set the total number of elements
public void setSize(int n) { //No change
sz = new int[n];
for (int i = 0; i < n; i++)
sz[i] = 1;
}

//return an identifier for the set containing a
public int find(int a){ //follow links to find a root
while (a != id[a])
a = id[a]; //pop
return a;
}//No change in this function as well

//merge the set containing a with the set containing b
public void union(int a, int b)
{

int i = find(a);
int j = find(b);
if (i == j) return;
/*
After finding the group leaders, we will create a UnionInfo object and contain
information about the groups and their sizes before the union operation so they can be reverted
back using deUnion operation
*/
UnionInfo x=new UnionInfo();
//make smaller root point to larger one
if (sz[i] < sz[j]) {
  
x.l1=j; //Setting values for UnionInfo object
x.l2=i;
x.size1=sz[j];
x.size2=sz[i];
id[i] = j; sz[j] += sz[i]; //Unchanged union statement
}
else {
x.l1=i; //Setting values for UnionInfo object
x.l2=j;
x.size1=sz[i];
x.size2=sz[j];
id[j] = i; sz[i] += sz[j]; //Unchanged union statement
}
stack.push(x); //Now we push this Union operation info object to stack
}

// undo the last union operation
public void deUnion(){
/*
In this function, we will create a UnionInfo object
and assign the top element from the stack to it.
Now, we will assign the leaders contained in this UnionInfo object
to themselves and reset their size to their previous size given by size1 and
size2
*/
UnionInfo a=new UnionInfo();
a=stack.peek();
id[a.l1]=a.l1; //Setting the leader of 1st group leader to itself
id[a.l2]=a.l2; //Setting the leader of 2nd group leader to itself
sz[a.l1]=a.size1; //Resetting the size of both the groups to their original
sz[a.l2]=a.size2; //size stored in the UnionInfo stack object
  
stack.pop(); //Pop the top element as this union operation has been undoed
}

//Return the number of elements in the set containing a
public int elementsInSet(int a){ //Made changes so that this function works as inteded
int sum = 0;
for (int i : id) {
if (find(i) == find(a)) //Used find instead of using the id array as we need to compare the group leader
sum++;
}
return sum;
}
  
}

public class Main //Main function to test functionality of deUnion
{
   public static void main(String[] args) {
       UFwithDeunion obj=new UFwithDeunion(10); //Created object for Union operation with 10 element
obj.union(1,2); //Grouping 1 and 2
obj.union(2,3); //Grouping 2 and 3 and the group is now(1,2,3)
obj.union(4,5); //Grouping 4 and 5
obj.union(4,6); //Grouping 4 and 6 and the group is now (4,5,6)
obj.union(3,4); //Grouping 3 and 4 and the group is now (1,2,3,4,5,6)
for(int i=0;i<10;i++) //Loop to view the leader of the group the elements are contained in
{
System.out.println(i+" "+obj.find(i));
//Would display element from 1 to 6 have leader set to 1
}
obj.deUnion(); //Calling the deUnion operation
//Now the groups should be (1,2,3) and (4,5,6)
for(int i=0;i<10;i++)
{
System.out.println(i+" "+obj.find(i));
//Now we would see that the latest deUnion operation is succesful
// as only 1,2 and 3 have their leaders set to 1 and
//4,5 and 6 have their leader set to 4
}
   }
}

Output: