算法刷题笔记--并查集的运用

1、题目描述：

一个城市中有两个犯罪团伙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

2、代码实现

#include<iostream>
#include<set>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>
#include<string>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=100005;
int father[N*2];
int find(int x)
{
	if(x!=father[x]) 
		father[x]= find(father[x]);
	return father[x];
}
void unionSet(int x,int y)
{
//	int fx=find(x);
//	int fy=find(y);
//	if(fx!=fy)
//	{
//		father[fy]=fx;
//	}
	father[find(y)]=find(x);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin.tie(0);
	
	int t,n,m;
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		for(int i=1;i<=n*2+1;i++)
		{
			father[i]=i;
		}
		string op;
		int a,b;
		while(m--)
		{
			cin>>op>>a>>b;
			if(op=="D")
			{
				unionSet(a,b+n);
				unionSet(a+n,b);
			}else
			{
				int fa=find(a);
				int fb=find(b);
				if(fa==fb)
				{
					cout<<"In the same gang."<<endl;
				}else if(fa==find(b+n) || fb==find(a+n))
				{
					cout<<"In different gangs."<<endl;
				}else
				{
					cout<<"Not sure yet."<<endl;
				}
			}
		}
	}
    return 0;
}