POJ 2236 Wireless Network ||POJ 1703 Find them, Catch them 并查集

标签：acm   编程   poj   并查集   

POJ 2236 Wireless Network

http://poj.org/problem?id=2236

题目大意：

给你N台损坏的电脑坐标，这些电脑只能与不超过距离d的电脑通信，但如果x和y均能C通信，则x和y可以通信。现在给出若干个操作，

O p 代表修复编号为p的电脑

S p q代表询问p和q是不是能通信。

思路：

并查集即可。。

如果修复了一台电脑，则把与它相连距离不超过d的且修复了的放在一个集合里面。

#include
#include
#include
using namespace std;
const int MAXN=1000+10;
int fa[MAXN],n,d;
bool canuse[MAXN];
int find(int cur)
{
	return fa[cur]


POJ 1703 Find them, Catch them 

http://poj.org/problem?id=1703

题目大意：
xx城市有两个帮派，给你m条信息，D a b表示a和b不在一个帮派里。A a b时要求输出a和b是不是在一个帮派里。（在/不在/不确定）
思路：
和这题POJ 1182 食物链 并查集差不多。

划分为两个集合，给出D a b 说明a和b不在一个集合，那么就合并a和b+n,b和a+n。



#include
#include
#include
using namespace std;
const int MAXN=200000+10;
int fa[MAXN];
int find(int cur)
{
	return cur==fa[cur]? cur: fa[cur]=find(fa[cur]);
}
void union_set(int a,int b)
{
	int root_a=find(a);
	int root_b=find(b);
	if(root_a==root_b)
		return;
	fa[root_a]=root_b;
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n,m;
		scanf("%d%d",&n,&m);
		int num=n*2;
		for(int i=1;i




POJ 2236 Wireless Network ||POJ 1703 Find them, Catch them 并查集,搜素材,soscw.com
POJ 2236 Wireless Network ||POJ 1703 Find them, Catch them 并查集
标签：acm   编程   poj   并查集   
原文地址：http://blog.csdn.net/murmured/article/details/24921257