【題目敘述】https://vjudge.net/problem/POJ-2236
【解題想法】並查集，Disjoint Set Union-Find algorithm (DSU)
- 兩台已經修復的電腦，如果其間的距離小於等於d，可以互相通訊。
- v[i]：讀入測資時，順便計算這台電腦 (i) 與前面電腦間的距離，紀錄電腦 i 可連結的所有電腦。(Line-25)
- p[i]：DSU，i 所屬集合的代表元素。初始值指向自己，p[i] = i。
- fix[i]：紀錄電腦 i 的修復狀態。當修復電腦 i 時，順便將其與v[i]中「已經修復的」電腦進行並查集合併 (Union)。(Line-36)
- 函式 Find( )：執行並查集的查詢功能。
- 查詢兩台電腦能否通訊時，只要查詢兩台電腦所屬集合的代表元素是否相同即可。(Line-40)
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
int n, d, a, b;
int x[1005], y[1005], fix[1005], p[1005];
vector <int> v[1005];
char c;
int Find(int x){
if (p[x] == x) return x;
p[x] = Find(p[x]);
return p[x];
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> d;
for (int i = 1; i <= n; i++){
cin >> x[i] >> y[i];
p[i] = i;
for (int j = 1; j < i; j++){
if ((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) <= d*d){
v[i].push_back(j);
v[j].push_back(i);
}
}
}
while (cin >> c){
if (c == 'O'){
cin >> a;
fix[a] = 1;
for (int i = 0; i < v[a].size(); i++){
if (fix[v[a][i]] == 1) p[Find(v[a][i])] = Find(a);
}
} else {
cin >> a >> b;
if (Find(a) == Find(b)) cout << "SUCCESS\n";
else cout << "FAIL\n";
}
}
return 0;
}