I’m getting a runtime error and I have no idea why. Can anybody help me? Here’s the Java code:
import java.io.*;
/**
- Created by Chris on 2/28/2015.
*/
//implement using disjoint sets with path compression
//sets will be unioned using a value associated with it instead of the rank
//the max of this value will be at the root of the set it belongs to
class DISHOWN {
private static int[][] sets;
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
static StreamTokenizer reader = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
private static int nextInt() throws IOException {
reader.nextToken();
return (int) reader.nval;
}
public static void main(String[] args) throws IOException {
int T = nextInt();
while (T-- > 0) {
int N = nextInt();
//sets[i][0] are the scores for the dishes
//sets[i][1] are the pointers to parents
//sets[i][1] == i, means it's a root
sets = new int[N + 1][2];
for (int i = 1; i <= N; i++) {
sets[i][0] = nextInt();
sets[i][1] = i;
}
int Q = nextInt();
while (Q-- > 0) {
int query = nextInt();
if (query == 1) {
int index = nextInt();
//do find
pw.println(find(index));
} else {
int index1 = nextInt();
int index2 = nextInt();
//do union
if (union(index1, index2) == -1) pw.println("Invalid query!");
}
}
}
pw.flush();
}
private static int find(int x) {
int result;
if (sets[x][1] == x) return x;
else result = find(sets[x][1]);
sets[x][1] = result;
return result;
}
//returns -1 if the elements belong to the same set
//otherwise performs the union and returns 1
private static int union(int x1, int x2) {
if (x1 == x2) return -1;
int parent1 = find(x1);
int parent2 = find(x2);
if (parent1 == parent2) return -1;
int diff = sets[parent1][0] - sets[parent2][0];
if (diff > 0) {
sets[parent2][1] = sets[parent1][1];
} else if (diff < 0) {
sets[parent1][1] = sets[parent2][1];
}
return 1;
}
}