【集训DAY13】Internet【并查集】

思路：

我们发现每次修理后只需要一个并查集就可以把相连的连上。

$code$

#include<iostream>
#include<cmath>
#include<cstdio>

using namespace std;

const int MAXN = 1010;

int n, d, fa[MAXN];

struct node {
    
	int x, y;
}a[MAXN];

bool v[MAXN];

double dis(int x, int y) {
    
	return sqrt((a[x].x - a[y].x) * (a[x].x - a[y].x) * 1.0 + (a[x].y - a[y].y) * (a[x].y - a[y].y) * 1.0);
}

int getfa(int x) {
    
	if(x == fa[x]) return x;
	return fa[x] = getfa(fa[x]);
}

int main() {
    
	scanf("%d%d", &n, &d);
	for(int i = 1; i <= n; i ++) scanf("%d%d", &a[i].x, &a[i].y), fa[i] = i;
	char ch;
	int x, y;
	scanf("%c", &ch);
	while(scanf("%c", &ch) != EOF) {
    
		if(ch == 'O') {
    
			scanf("%d", &x);
			v[x] = 1;
			for(int i = 1; i <= n; i ++) {
    
				if(v[i] && dis(x, i) <= d * 1.0) {
    
					int xx = getfa(x), yy = getfa(i);
					if(xx == yy) continue;
					fa[xx] = yy;
				}
			}
		}
		else {
    
			scanf("%d%d", &x, &y);
			if(!v[x] || !v[y])  {
    
				printf("FAIL\n");
				scanf("%c", &ch);
				continue;
			}
			int xx = getfa(x), yy = getfa(y);
			if(xx == yy) printf("SUCCESS\n");
			else printf("FAIL\n");
		}
		scanf("%c", &ch);
	}
	return 0;
}