题目大意：两个黑社会帮派，互相打架，现在你很多条信息，要你确定两个人是否属于不同帮派
这题很有趣，题目不是直接给你两个人是否是一个帮派的，他给你的是不同帮派的，也就是给你很多个不同的要你找相同的。
乍看很麻烦，但是还记得我以前发布过一个食物链的题解吗！
食物链要求维护三个不同关系的集合，我第二种方法用的是偏移集！只用两个集合就搞定问题了。
这一题比食物链更简单，他只用维护两个就可以了。
1 #include <iostream> 2 #include <functional> 3 #include <algorithm> 4 #define MAX 100005 5 6 using namespace std; 7 typedef int Position; 8 9 static int Set[MAX]; 10 static int delta[MAX]; 11 12 Position Find(Position); 13 void Unite_Set(Position, Position); 14 void Test(Position, Position); 15 16 int main(void) 17 { 18 int case_sum, n, message_sum, tmp_x, tmp_y; 19 char choice; 20 scanf("%d", &case_sum); 21 while (case_sum--) 22 { 23 scanf("%d%d", &n, &message_sum); 24 getchar(); 25 for (int i = 1; i <= n; i++) 26 Set[i] = i; 27 memset(delta, 0, sizeof(delta)); 28 for (int i = 0; i < message_sum; i++) 29 { 30 scanf("%c", &choice); 31 scanf("%d%d", &tmp_x, &tmp_y); 32 if (choice == 'D') 33 Unite_Set(tmp_x, tmp_y); 34 else 35 Test(tmp_x, tmp_y); 36 getchar();//消除回车 37 } 38 } 39 return 0; 40 } 41 42 void Test(Position x, Position y) 43 { 44 Position px, py; 45 px = Find(x); py = Find(y); 46 if (px == py) 47 { 48 if ((delta[x] - delta[y] + 2) % 2 == 0) 49 puts("In the same gang."); 50 else 51 puts("In different gangs."); 52 return ; 53 } 54 puts("Not sure yet."); 55 } 56 57 Position Find(Position x) 58 { 59 Position tmp; 60 if (Set[x] == x) 61 return x; 62 tmp = Find(Set[x]); 63 64 delta[x] = (delta[x] + delta[Set[x]]) % 2; 65 Set[x] = tmp; 66 return tmp; 67 } 68 69 void Unite_Set(Position x, Position y) 70 { 71 Position px, py; 72 px = Find(x); py = Find(y); 73 if (px != py) 74 { 75 Set[py] = px; 76 delta[py] = (delta[x] - delta[y] + 1 + 2) % 2; 77 } 78 }
