The police office in Tadu City decides to say ends to the chaos, as launch actions to root up the TWO gangs in the city, Gang Dragon and Gang Snake. However, the police first needs to identify which gang a criminal belongs to. The present question is, given two criminals; do they belong to a same clan? You must give your judgment based on incomplete information. (Since the gangsters are always acting secretly.)
Assume N (N <= 10^5) criminals are currently in Tadu City, numbered from 1 to N. And of course, at least one of them belongs to Gang Dragon, and the same for Gang Snake. You will be given M (M <= 10^5) messages in sequence, which are in the following two kinds:
1. D [a] [b]
where [a] and [b] are the numbers of two criminals, and they belong to different gangs.
2. A [a] [b]
where [a] and [b] are the numbers of two criminals. This requires you to decide whether a and b belong to a same gang.
Input
The first line of the input contains a single integer T (1 <= T <= 20), the number of test cases. Then T cases follow. Each test case begins with a line with two integers N and M, followed by M lines each containing one message as described above.
Output
For each message "A [a] [b]" in each case, your program should give the judgment based on the information got before. The answers might be one of "In the same gang.", "In different gangs." and "Not sure yet."
Sample Input
1
5 5
A 1 2
D 1 2
A 1 2
D 2 4
A 1 4
Sample Output
Not sure yet.
In different gangs.
In the same gang.
題意：輸入n和m，代表有n個人和m個詢問，n個人分别屬于兩個幫派，每個詢問遵循下面的規則：
A a b要求輸出a與b是否在同一個幫派。
D a b告訴資訊a和b是不同幫派的成員。
不是基本的并查集，可能有多個集合。
比如輸入D 1 2 D 3 4 D 5 6...這就至少有3個集合了。
并且任意2個集合之間成員的敵我關系不明。
同一個集合裡，關系明确，敵人或朋友。
不能簡單認為成朋友在一個集合，敵人在另外一個集合，分成2個集合。
因為題目說隻有2個匪幫，很容易進入這個誤區。
怎麼分類呢？經典的方法，用x,x+n分别代表x屬于A類和x屬于B類。
怎麼合并呢？比如告訴你x和y不在一個集合，那麼就是兩種可能，x-A，y-B或者x-B，y-A，我們把x，y+n合并，再把y，x+n合并。同一棵樹上的時間同時發生或者同時不發生。也就是說，若x-A，則y一定屬于B。
怎麼查詢呢？如果x和y在一棵樹上，或者x+n和y+n在一棵樹上，就是同一個黑幫的。如果x和y+n在同一棵樹上，或者x+n和y在同一棵樹上，就是不同的黑幫。否則不能判斷。
案例分析：
1
5 5
A 1 2 Not sure yet.
D 1 2
A 1 2 In different gangs.
D 2 4
A 1 4 In the same gang.
參考網站：
https://blog.csdn.net/say_c_box/article/details/50893928
https://blog.csdn.net/yinghui_yht/article/details/53363012
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int fa[200005];//注意數組大小 100005錯誤runtime error
int find(int x)
{
if(fa[x]==x)
return x;
return fa[x]=find(fa[x]);
}
bool same(int x,int y){
return find(x)==find(y) ;
}
void bind(int x,int y)
{
int fx=find(x);
int fy=find(y);
if(fx!=fy)
fa[fx]=fy;
}
int main()
{
int t, n,m,x,y;
char c;
scanf("%d",&t);
while(t--){
scanf("%d %d",&n,&m);
for(int i=1;i<=2*n;i++) fa[i]=i;
while(m--)
{
getchar();
scanf(" %c %d %d",&c,&x,&y);
if(c=='A'){
if(same(x,y)||same(x+n,y+n)) //同類
printf("In the same gang.\n");
else if(same(x+n,y)||same(x,y+n))//不同類
printf("In different gangs.\n");
else printf(("Not sure yet.\n"));
}
//D
else {
bind(x,y+n);
bind(x+n,y);
}
}
}
return 0;
}
/*對D的補充說明
x和y不在一個集合
那麼就是兩種可能，x-A，y-B或者x-B，y-A
我們把x，y+n合并，再把y，x+n合并。
同一棵樹上的時間同時發生或者同時不發生。
也就是說，若x-A，則y一定屬于B。*/
Runtime Error大概有這幾種：
Runtime Error(ARRAY_BOUNDS_EXCEEDED) // array bounds exceed 數組越界
Runtime Error(DIVIDE_BY_ZERO) //divisor is nil 除零
Runtime Error(ACCESS_VIOLATION) //illegal memory access 非法記憶體讀取
Runtime Error(STACK_OVERFLOW) //stack overflow 系統棧過載
具體解決辦法：
檢查一下數組、指針是否越界；
是否除0；
檢查一下小數組是否符合題意，可以把數組開的大一些；
檢查一下局部數組變量是否過大。
在此題中我改了一下fa[]數組大小