POJ2236题解

这道题可以说是并查集板子题了

我们做一个初始化：

我们把每一台电脑看做一个点，我们将每一个点与它能通信的点连一条边

就是代码里的这一段

for(register int i=1;i 
然后跑一遍并查集：
 
做 "O" 操作的时候把修复好的电脑与其他可通信范围内的好电脑并集，有了前面的初始化，这里就不用一个个枚举了（本人表达能力不好，说话有点绕）
 
在做 "S" 操作的时候就判断他们两个是否在同一个集合里
 
AC代码 
 
​#include
#include
#include
#include
using namespace std;

const int N=1009;

int n,d,x[N],y[N],f[N],p,q;//x记x坐标,y记y坐标,f[i]记i的父亲
char c;
bool vis[N];//vis记它有没有被修复,0表示没有,1表示有

vectore[N];//e[x][j]=y表示x有一条边到边y,且是第j条边

int find(int x){ //找到x所在集合的根
	if(f[x]==x)return x;
	return f[x]=find(f[x]);
}

int main(){
	scanf("%d%d",&n,&d);
	
	for(register int i=1;i<=n;i++)f[i]=i;//初始化f,个人喜欢这么写
	
	for(register int i=1;i<=n;i++)
		scanf("%d%d",&x[i],&y[i]);
	
	for(register int i=1;i>c){
		if(c=='0'||c=='O'){
			scanf("%d",&p);
			vis[p]=1;
			for(register int i=0;i 
谢谢