POJ - 2236Wireless Network(并查集)
标签:network poj puts 遍历 strong ++i ons set nio
并查集。
每次修理计算机,遍历可以与之相连的计算机并进行合并。时间复杂度 \(O(n\log n)\) 。最多只用修理 \(n\) 次。
每次测试连通性,判断根节点是否相同,时间复杂度 \(O(1)\) 。最多不过 \(3e5\) 次测试。
总时间复杂度 \(O(3e5+n^2\log n)\) 。
#include <cstdio> #include <vector> using namespace std; /** * Disjoint Set Union */ class DSU { vector<int> s; int cnt; public: DSU(int n) { cnt = n; s.resize(n+1); for (int i = 1; i <= n; ++i) s[i] = i; } int find(int x) { if (x != s[x]) s[x] = find(s[x]); return s[x]; } bool unite(int u, int v) { int x = find(u); int y = find(v); if (x != y) { s[y] = x; --cnt; return true; } return false; } int getCnt() { return cnt; } }; const int N = 1003; struct P { int x, y; int to2(const P &t) { return (x-t.x)*(x-t.x)+(y-t.y)*(y-t.y); } } p[N]; bool ok[N]; int main() { int n, d; scanf("%d%d", &n, &d); for (int i = 1; i <= n; ++i) { scanf("%d%d", &p[i].x, &p[i].y); } DSU dsu(n); char op; while (~scanf("%c", &op)) { if (op == ‘O‘) { int u; scanf("%d", &u); if (ok[u]) continue; for (int i = 1; i <= n; ++i) if (ok[i] && p[u].to2(p[i]) <= d*d) dsu.unite(u, i); ok[u] = true; } else if (op == ‘S‘) { int u, v; scanf("%d%d", &u, &v); if (dsu.find(u) == dsu.find(v)) puts("SUCCESS"); else puts("FAIL"); } } return 0; }
POJ - 2236Wireless Network(并查集)
标签:network poj puts 遍历 strong ++i ons set nio
原文地址:https://www.cnblogs.com/zbhfz/p/14463780.html