POJ 1703 Find them、Catch them【種類と検索集】

Find them,Catch them
Time Limit: 1000 MS
 
メモリLimit: 100000 K
Total Submissions: 54120
 
Acceepted: 16572
Description
The police office in Tadu City decides to say ends to the chaos、as lanch actions to root up the TWO gangs in the city、Gang Dragon and Gang Snake.However、the police first need to idadis to whiggantife.The Bentings.The.ドthey belong to a same clan?You must give your judment based on incompplete information.(Since the gangsters are always ting secretly.)  Asume N(N<=10^5)criminals are currently in Tadu City,numbed from 1 to N.And of course,at least one of them belongs to Gang Dragon,and the same for Gang Snake.You will given M(M=10 the mechanges)  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.The n T T cases follow.Each test case begins with a line with two integers N and M,folled by mys inease
Output
For each message「A[a][b]」in each case,your program shuld give the judment based on the information got before.The answers might be one of「In the same gang.」
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.

ソurce
POJ Monthly-2010.7.18
問題リンク:POJ 1703 Find them、Catch them
問題の説明:N個(1から番号)を与えられました.このN個は一人当たり2つのグループの中の一つです.M回の操作で、D aとbは同じグループではないことを示し、A bはaとbが同じグループにあるかどうかを調べ、出力Not sure yetを特定できない.In different gangsは同じグループに出力されない.In the same gangは同じグループに出力される.
問題の考え方:種類を調べて集めます.pre記憶iの親ノードrはiと親ノードの関係を記憶し、0はiと親ノードは同じグループであり、1は同じグループではないことを表す.コードを具体的に見る
ACのC++コード:

#include

using namespace std;

const int N=100010;

int pre[N],r[N];//pre  i     r  i       ，0  i        ，1        
void init(int n)
{
	for(int i=0;i<=n;i++){
		pre[i]=i;//          
		r[i]=0;//          
	}
}

int find(int x)
{
	if(x!=pre[x]){
		int rt=pre[x];
		pre[x]=find(rt);
		r[x]^=r[rt];
	}
	return pre[x];
}

void join(int x,int y)
{
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy){//fx fy    ，   
		pre[fy]=fx;
		r[fy]=1^r[x]^r[y];// fy     fx   ：y fy    r[y],y x    1，x fx    r[x], 
	}
}

int main()
{
	int n,m,t,a,b,x;
	char c;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		init(n);
		while(m--){
			scanf(" %c%d%d",&c,&a,&b);
			if(c=='D')
			  join(a,b);
			else if(c=='A'){
				int fa=find(a);
				int fb=find(b);
				if(fa!=fb)
				  printf("Not sure yet.
");
				else{
					if(r[a]!=r[b])
					  printf("In different gangs.
");
					else
					  printf("In the same gang.
");
				}
			}
		}
	}
	return 0;
}