题目：http://poj.org/problem?id=1703
依然并查集。
这题目比较悲剧的是使用Scanner会TLE，用BufferReader就过了。
以下crim[][0]存储父节点。
crim[][1]存储对立的人，通过find(crim[][1])操作可以找到对立人所在的集合，初始化为-1
1 import java.util.*;
2 import java.io.*;
3
4 public class Main {
5
6 static int[][] crim = new int[100001][2];
7 static int find(int a) {
8 if (crim[a][0] == a) return a;
9 crim[a][0] = find(crim[a][0]);
10 return crim[a][0];
11 }
12 static void union(int a, int b) {
13 crim[find(a)][0] = find(b);
14 }
15 static void init(int n) {
16 for (int i = 1; i < n+1; i++) {
17 crim[i][0] = i;
18 crim[i][1] = -1;
19 }
20 }
21
22 public static void main(String[] args) throws Exception {
23 BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
24 int t = Integer.valueOf(cin.readLine());
25 while (t-- > 0) {
26 String[] nm = cin.readLine().split(" ");
27 int n = Integer.valueOf(nm[0]);
28 int m = Integer.valueOf(nm[1]);
29 init(n);
30 while (m-- > 0) {
31 String[] next = cin.readLine().split(" ");
32 char type = next[0].charAt(0);
33 int a = Integer.valueOf(next[1]);
34 int b = Integer.valueOf(next[2]);
35 if (type == 'D') {
36 if (crim[a][1] == -1) crim[a][1] = b;
37 else union(crim[a][1], b);
38 if (crim[b][1] == -1) crim[b][1] = a;
39 else union(crim[b][1], a);
40 } else { // type == 'A'
41 int pa = find(a);
42 int pb = find(b);
43 if (pa == pb) {
44 System.out.println("In the same gang.");
45 } else if ((crim[a][1] != -1 && find(crim[a][1]) == pb) ||
46 (crim[b][1] != -1 && find(crim[b][1]) == pa)) {
47 System.out.println("In different gangs.");
48 } else {
49 System.out.println("Not sure yet.");
50 }
51 }
52 }
53 }
54 }
55 }