Find them, Catch them
A tyical uses of union find. To solve this type of problem, we have two different approach.
One is re-encode the relationships. Let's say we have two class A
and B
, once given two
people a
and b
can not be in the same class, that means either a in A and b in B
and
b in A and a in B
is true. We use a-A
, a-B
, b-A
and b-B
to stands for each containing
states. Then if two states should appears at the same time, we union them in union find set.
For a people numbered i
and total people count N
, we use 0 ~ N - 1
to stands for i-A
,
N ~ 2N - 1
to stands for i-B
, then we can query relationship or union two state easily.
This solution is easily to understand and implment and applys to multiple classes questions.
Also this solution is not vulnerable to StackOverflowError
. But it will cost more spaces.
import java.io.*;
import java.util.*;
public class FindThemCatchThem {
static int[] ids;
static int[] rank;
public static void main(String[] args) throws Exception {
BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(buf.readLine());
for (int i = 0; i < t; i++) {
String str[] = buf.readLine().split(" ");
int n = Integer.parseInt(str[0]);
int m = Integer.parseInt(str[1]);
ids = new int[n + 1];
rank = new int[n + 1];
for (int j = 0; j < ids.length; j++) {
ids[j] = j;
}
for (int j = 0; j < m; j++) {
str = buf.readLine().split(" ");
String op = str[0];
int a = Integer.parseInt(str[1]);
int b = Integer.parseInt(str[2]);
if (op.equals("D")) {
union(a, b);
} else {
if(n == 2)
System.out.println("In different gangs.");
else if(find(a)==find(b)){
if(rank[a] == rank[b])
System.out.println("In the same gang.");
else
System.out.println("In different gangs.");
}else
System.out.println("Not sure yet.");
}
}
}
}
private static void union(int p, int q) {
int pid = find(p);
int qid = find(q);
ids[pid] = qid;
rank[pid] = (rank[p] + rank[q] + 1) % 2;
}
private static int find(int p) {
if (ids[p] == p) return p;
int root = find(ids[p]);
rank[p] = (rank[p] + rank[ids[p]]) % 2;
return ids[p] = root;
}
}
Another solution is that we uses rank values to mark if current node is in the same class of it's parent
node. If it is the same, we use 0
, or we use 1
. Then when we are peforming find and union operation,
we should handle and update the rank values correctly. In this implementation, we have to use recursive
way to perform find operation and after find we point current node directly to its final root.
The new rank is decided by current rank and it's old parent's new rank. As after the recursion,
currently the parent node is directly point to root. So parent node p
, root node rt
and current node c
has the following relationships:
p
andrt
in same clas,c
andp
in same class, thenc
and rt in same classp
andrt
not in same clas,c
andp
not in same class, thenc
and rt in same class- Otherwise,
c
andrt
not in same class
The relationships above can be represented with a consice expression: (rank[c] + rank[p]) % 2
.
Also, when perform union, we have to handle similar things too. Let p
and q
be two roots of
two elements to union, the corresponding expression will be (rank[p] + rank[q] + 1) % 2
.
This solution is a little hard to understand and not easy to be implemented right, it is also
vulnerable to StackOverflow
. But this solution can be inducted to muliple classes questions and also
more save in space.
import java.io.*;
import java.util.*;
public class FindThemCatchThem2 {
static int[] ids;
static int[] sizes;
public static void main(String[] args) throws Exception {
BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(buf.readLine());
for (int i = 0; i < t; i++) {
String str[] = buf.readLine().split(" ");
int n = Integer.parseInt(str[0]);
int m = Integer.parseInt(str[1]);
ids = new int[n * 2];
sizes = new int[n * 2];
for (int j = 0; j < ids.length; j++) {
ids[j] = j;
sizes[i] = 1;
}
for (int j = 0; j < m; j++) {
str = buf.readLine().split(" ");
String op = str[0];
int a = Integer.parseInt(str[1]) - 1;
int b = Integer.parseInt(str[2]) - 1;
if (op.equals("D")) {
union(a, b + n);
union(a + n, b);
} else {
if(connected(a, b))
System.out.println("In the same gang.");
else if(connected(a, b + n)){
System.out.println("In different gangs.");
}else
System.out.println("Not sure yet.");
}
}
}
}
private static void union(int p, int q) {
int pid = find(p);
int qid = find(q);
if (sizes[pid] < sizes[qid]) {
ids[pid] = qid;
sizes[qid] += sizes[pid];
} else {
ids[qid] = pid;
sizes[pid] += sizes[qid];
}
}
private static int find(int p) {
while (p != ids[p]) {
ids[p] = ids[ids[p]];
p = ids[p];
}
return p;
}
private static boolean connected(int p, int q) {
return find(p) == find(q);
}
}