发现它,抓住它

3:发现它,抓住它

  • 查看
  • 提交
  • 统计
  • 提问
总时间限制: 
1000ms 
内存限制: 
65536kB
描述
一个城市中有两个犯罪团伙A和B,你需要帮助警察判断任意两起案件是否是同一个犯罪团伙所为,警察所获得的信息是有限的。假设现在有N起案件(N<=100000),编号为1到N,每起案件由团伙A或团伙B所为。你将按时间顺序获得M条信息(M<=100000),这些信息分为两类:
1. D [a] [b]
其中[a]和[b]表示两起案件的编号,这条信息表明它们属于不同的团伙所为

2. A [a] [b]
其中[a]和[b]表示两起案件的编号,这条信息需要你回答[a]和[b]是否是同一个团伙所为
注意你获得信息的时间是有先后顺序的,在回答的时候只能根据已经接收到的信息做出判断。


输入
第一行是测试数据的数量T(1<=T<=20)。
每组测试数据的第一行包括两个数N和M,分别表示案件的数量和信息的数量,其后M行表示按时间顺序收到的M条信息。
输出
对于每条需要回答的信息,你需要输出一行答案。如果是同一个团伙所为,回答"In the same gang.",如果不是,回答"In different gangs.",如果不确定,回答”Not sure yet."。
样例输入
1
5 5
A 1 2
D 1 2
A 1 2
D 2 4
A 1 4
样例输出
Not sure yet.
In different gangs.
In the same gang.
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
using namespace std;
int father[100005];
int tag[100005];
int Getfather(int x)
{
	if(x==father[x])return x;
	int tmp=Getfather(father[x]);
	tag[x]=(tag[x]+tag[father[x]])%2;
	father[x]=tmp;
	return tmp;
}
int main()
{
	int Test,n,k,x,y;
	char c;
	cin>>Test;
	while(Test--)
	{
		cin>>n>>k;
		for(int i=1;i<=n;++i)
		{
			father[i]=i;
			tag[i]=0;
		}
		while(k--)
		{
			cin>>c>>x>>y;
			int fx=Getfather(x);
			int fy=Getfather(y);
			if(c=='A')
			{
				if(fx!=fy)
				{
					cout<<"Not sure yet."<<endl;
				}
				else
				{
					if(tag[x]==tag[y]) cout<<"In the same gang."<<endl;
					else cout<<"In different gangs."<<endl;
				}
			}
			else
			{
				father[fx]=fy;
				tag[fx]=(tag[y]-tag[x]+1)%2;
			}
		}
	}
	return 0;
}