im learning some algorithms , and trying to come up with a version for Quick find using union find.
the algorithm works like :
1. get user input for size of the array (the array holds the data on which quickfind will work)
2. create and initialize the array based on the input size.
3. get user user input of two numbers, these are the indices of the array, and check if the values at these positions are same, then they are declared connected.
4. if not connected, ie, values at the positions aren't the same, connect/union them.. ie make them have same values.
n so on...
the problem im facing is that the array keeps re-initializing, so changes made in one iteration dont show up in the next, so connected() method doesnt work.. n im in a mess.
any help would be great :)
this is the code i came up with:
public class UF {
public static void main(String [] args){
inputHelper reader = new inputHelper();
int size=0,toChange=0,changeWith=0,connected=0;
size = reader.getMyIntger("enter size of array ");
QuickFindUF tester = new QuickFindUF(size);
while(connected != size){
System.out.println("enter value pair to check: ");
toChange = reader.getMyIntger(" ");
changeWith = reader.getMyIntger(" ");
if( !tester.connected(toChange, changeWith) ){
tester.union(toChange, changeWith);
connected++;
System.out.println("connection : " + toChange + " and " + changeWith + " total connections : " + connected);
}
else{
System.out.println("already connected");
}
}
System.out.println("all connected, exiting program..");
}
}
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class inputHelper {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
public int getMyIntger(String prompt){
System.out.print(prompt + " : ");
String ip = null;
int num = 0;
try{
ip = in.readLine();
num = Integer.parseInt(ip);
}catch(IOException e){
System.out.println("IOException : " + e);
}catch(NumberFormatException e){
System.out.println("thats not a number!!");
}
return num;
}
public String getMyString(String prompt){
System.out.print(prompt + " : ");
String ip = null;
try{
ip = in.readLine();
if(ip.length() == 0)
return null;
}catch(IOException e){
System.out.println("IOException : " + e);
}
return ip;
}
}
public class QuickFindUF {
private int[] id;
int connects = 0,tcid=0,cwid=0;
public QuickFindUF(int n){
System.out.print("\nin constructor... ");
id = new int[n];
for(int i = 0; i<n ; i++){
id[i] = i;
}
for(int i : id)
System.out.print(i + " ");
}
public boolean connected(int p, int q){
System.out.print("\nin connected... ");
if(id[p]==id[q])
System.out.println("connected");
return(id[p]==id[q]);
}
public void union(int toChange, int changeWith){
System.out.print("in union: ");
tcid = id[toChange];
cwid = id[changeWith];
System.out.format("id[%d] = %d , id[%d] = %d ",toChange,tcid,changeWith,cwid);
for(int i = 0; i < id.length ; i++){
if( id[i] == tcid ){
tcid = cwid;
}
}
System.out.format("id[%d] = %d , id[%d] = %d ",toChange,tcid,changeWith,cwid);
}
}
note: i copy-pasted the contents of the 3 classes one after another, so the import statements and a few others might seem at odd places. i didnt want to tamper with the lines here and introduce further error, so i kept it as it is. sorry for that...
regards
somjit.
