> Source
> 
> Problem Id:1703  User Id:yangguo981 
> Memory:484K  Time:609MS
> Language:C++  Result:Wrong Answer
> 
> Source 
> 
> #include <numeric>
> #include <vector>
> #include <deque>
> #include <queue>
> #include <set>
> #include <map>
> #include <string>
> #include <stack>
> #include <algorithm>
> #include <functional>
> #include <iterator>
> #include <cmath>
> #include <iostream>
> #include <sstream>
> #include <fstream>
> #include <list>
> #include <bitset>
> using namespace std;
> 
> typedef pair<int, int> PII;
> 
> #define BE(a) (a).begin(),(a).end()
> #define FOR(i,j,k) for((i)=(j); (i)<(k); ++(i))
> #define REP(i,n) FOR((i), 0, (n))
> #define LENGTH(x) (sizeof((x))/sizeof(((x)[0])))
> 
> int T,N,M;
> int parent[1000001];
> //vector<int> parent;
> PII getRoot(int x){
> 	int level = 0;
> 	while(parent[x] >= 0)
> 		x = parent[x],
> 		++level;
> 	return PII(x, level);
> }
> void merge(int x, int y){
> 	int r1 = getRoot(x).first;
> 	int r2 = getRoot(y).first;	
> 	if (r1 == r2) return;
> 	int level1 = getRoot(x).second;
> 	int level2 = getRoot(y).second;
> 	int count1 = parent[r1];
> 	int count2 = parent[r2];
> 	//x->y
> 	if (level1 > level2){
> 		int current = x,
> 		next = parent[current];
> 		while(next >= 0){
> 			int temp = parent[next];
> 			parent[next] = current;
> 			current = next;
> 			next = temp;
> 		}
> 		//parent[next] = current;
> 		parent[r2] += count1;
> 		parent[x] = y;
> 	}
> 	//y->x
> 	else{
> 		int current = y,
> 		next = parent[current];
> 		while(next >= 0){
> 			int temp = parent[next];
> 			parent[next] = current;
> 			current = next;
> 			next = temp;
> 		}
> 		//parent[next] = current;
> 		parent[r1] += count2;
> 		parent[y] = x;
> 	}
> }
> int main(){
> 	//ifstream cin("1.txt");
> 	cin >> T;
> 	while(T--){
> 		//cin >> N >> M;
> 		scanf("%d%d",&N,&M);
> 		char sign;
> 		int a,b,i;
> 		REP(i,N) parent[i] = -1;
> 		//parent.assign(N, -1);
> 		while(M--){
> 			//cin >> sign >> a >> b;
> 			cin >> sign;scanf("%d%d",&a,&b);
> 			if (sign == 'A'){
> 				PII p1 = getRoot(a);
> 				PII p2 = getRoot(b);
> 				if (p1.first != p2.first)
> 					printf("Not sure yet1.\n");
> 				else if (p1.second%2 == p2.second%2)
> 					printf("In the same g1ang.\n");
> 				else 
> 					printf("In differ2ent gangs.\n");
> 			}
> 			else merge(a, b);
> 		}
> 	}
> 	return 0;
> }
>