Wireless Network

裸的并查集，每次修好一个点之后就扫一遍，将它与在它连接范围内的之前就修好的点进行合并，唯一需要注意的点就是可以用点之间距离的平方来避免精度问题

#include <cstdio> #include <iostream> #include <cmath> const int MAXN = 10000 + 5; struct Point { int x, y; } point[MAXN]; struct Union_Find { int dad[MAXN]; int n; void init() { for (int i = 1; i <= n; i++) dad[i] = i; } Union_Find(int n) { this->n = n; init(); } int find(int x) { if (dad[x] != x) dad[x] = find(dad[x]); return dad[x]; } void merge(int x, int y) { dad[find(x)] = find(y); } bool judge(int x, int y) { return find(x) == find(y); } }; int n, d; bool is_fixed[MAXN]; int dis(Point a, Point b) { int ans = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y); return ans; } int main() { scanf("%d %d", &n, &d); d *= d; Union_Find uf(n); for (int i = 1; i <= n; i++) { scanf("%d %d", &point[i].x, &point[i].y); } char f; while (std::cin >> f) { if (f == 'O') { int x; scanf("%d", &x); is_fixed[x] = true; for (int i = 1; i <= n; i++) { if (i == x) continue; if (is_fixed[i] && dis(point[i], point[x]) <= d) uf.merge(x, i); } } else { int x, y; scanf("%d %d", &x, &y); uf.judge(x, y) ? puts("SUCCESS") : puts("FAIL"); } } return 0; }

The Suspects

这道题需要询问带元素 $0$ 的集合的元素个数，可以开一个数组 $sum[i]$ ，表示以 $i$ 为根节点的集合的元素个数，因为每个集合的元素个数都保存在根节点上了，所以在合并和输出的时候都要找到根节点来进行操作

#include <cstdio> #include <algorithm> const int MAXN = 30000 + 2; int n, m; struct Union_Find { int dad[MAXN], sum[MAXN]; int n; void init() { for (int i = 0; i < n; i++) { dad[i] = i; sum[i] = 1; } } Union_Find(int n) { this->n = n; init(); } int find(int x) { if (dad[x] != x) dad[x] = find(dad[x]); return dad[x]; } void merge(int a, int b) { int x = find(a); int y = find(b); if (x != y) { dad[y] = x; sum[x] += sum[y]; } } }; int main() { while (scanf("%d %d", &n, &m) != EOF) { if (n == 0 && m == 0) break; Union_Find uf(n); for (int i = 1; i <= m; i++) { int k; scanf("%d", &k); int x, y; scanf("%d", &x); k--; while (k--) { scanf("%d", &y); uf.merge(x, y); } } printf("%d\n", uf.sum[uf.find(0)]); } return 0; }

How Many Tables

每次合并都会少一个桌子，所以维护一个 $sum$ 表示桌子的数量即可

#include <cstdio> #include <algorithm> const int MAXN = 1000 + 5; struct Union_Find { int dad[MAXN]; int n, sum; void init() { for (int i = 1; i <= n; i++) dad[i] = i; sum = n; } Union_Find(int n) { this->n = n; init(); } int find(int x) { if (dad[x] != x) dad[x] = find(dad[x]); return dad[x]; } void merge(int x, int y) { dad[find(x)] = find(y); sum--; } bool judge(int x, int y) { return find(x) == find(y); } }; int main() { int t; scanf("%d", &t); while (t--) { int n, m; scanf("%d %d", &n, &m); Union_Find uf(n); for (int i = 1; i <= m; i++) { int x, y; scanf("%d %d", &x, &y); if (!uf.judge(x, y)) uf.merge(x, y); } printf("%d\n", uf.sum); } return 0; }

施工中