POJ 2236 Wireless Network
解法
Union-Find木を使って連結状態的なものを持っておく。
コンピュータpを修理したとき、他の修理されたコンピュータの中で距離d以内のものとuniteする
同じ根を持てば、通信可能である。
#include <cstdio> #include <algorithm> using namespace std; typedef pair<int, int> P; const int MAX_N = 1024; int N, d; P a[MAX_N]; int uf[MAX_N]; bool b[MAX_N]; void init(){ for(int i = 0; i < N; i++){ uf[i] = i; b[i] = false; } } int get_root(int p){ if(uf[p] == p) return p; int t = get_root(uf[p]); return uf[p] = t; } bool is_same(int p, int q){ int s = get_root(p); int t = get_root(q); return (s==t); } void unite(int p, int q){ int t = get_root(p); int s = get_root(q); uf[t] = s; } void rep(int p){ b[p] = true; for(int i = 0; i < N; i++){ if(p == i) continue; if(!b[i]) continue; int t = a[i].first - a[p].first; int s = a[i].second - a[p].second; if(t * t + s * s <= d * d){ if(!is_same(p, i)) unite(p, i); } } } int main(){ scanf("%d %d", &N, &d); for(int i = 0; i < N; i++){ int x, y; scanf("%d %d", &x, &y); a[i] = P(x, y); } init(); char c, op; scanf("%c", &c); while(scanf("%c", &op) != EOF){ if(op == 'O'){ //repairing int p; scanf("%d", &p); rep(p-1); }else{ int p, q; scanf("%d %d", &p, &q); if(is_same(p-1, q-1)) puts("SUCCESS"); else puts("FAIL"); } scanf("%c", &c); } return 0; }