PAT甲级刷题记录-(AcWing)-Day11(并查集 3题)

课程来源AcWing
其中AcWing中的题目为翻译好的中文题目

1013 Battle Over Cities

AcWing链接
PAT链接

#include <iostream>const int N = 1010;
using namespace std;
int p[N], n, m, k;
struct Edge {int a, b;
} edge[N * N];int find(int x) {if (p[x] != x) p[x] = find(p[x]);return p[x];
}int main() {scanf("%d %d %d", &n, &m, &k);for (int i = 0; i < m; ++i)scanf("%d %d", &edge[i].a, &edge[i].b);while (k--) {int x;scanf("%d", &x);// 初始化并查集for (int i = 0; i < n; ++i) {p[i] = i;}int cnt = n - 1; // 除去x城市外,其他的城市最多有21个连通量// 遍历每条边,将除了x外的边能合并的合并for (int i = 0; i < m; ++i) {int a = edge[i].a, b = edge[i].b;if (a != x && b != x) {int pa = find(a), pb = find(b); // 找a,和b的祖先是什么if (pa != pb) {//合并pa和pb两个并查集p[pa] = pb;cnt--; // 连通分量减一}}}printf("%d\n", cnt - 1);}return 0;
}

1114 Family Property

AcWing链接
PAT链接

解析
使用边来存储各个节点之间的关系
用并查集来合并同一个家庭
在合并的过程中让id最小的节点作为根,并将其他家庭成员的值累加到根上,方便最后输出

#include <iostream>
#include <vector>
#include <algorithm>const int N = 10100;
using namespace std;
int n;
int cnt[N], estate[N], area[N], idx;
bool visit[N];
struct Edge {int a, b;
} e[N];
int p[N];struct Family {int id;int number, estate, area;bool operator<(const Family &t) const {if (area * t.number != t.area * number) return area * t.number > t.area * number;return id < t.id;}
};int find(int x) {if (p[x] != x) p[x] = find(p[x]);return p[x];
}int main() {cin >> n;int tmp = n;while (tmp--) {int id, father, mother, k;cin >> id >> father >> mother >> k;visit[id] = true;if (father != -1) e[idx++] = {id, father};if (mother != -1) e[idx++] = {id, mother};while (k--) {int son;cin >> son;e[idx++] = {id, son};}cin >> estate[id] >> area[id];}for (int i = 0; i < N; ++i) {p[i] = i;cnt[i] = 1;}for (int i = 0; i < idx; ++i) {int a = e[i].a, b = e[i].b;visit[a] = visit[b] = true;int pa = find(a), pb = find(b);if (pa != pb) {if (pa > pb) swap(pa, pb);estate[pa] += estate[pb];area[pa] += area[pb];cnt[pa] += cnt[pb];p[pb] = pa;}}vector<Family> res;for (int i = 0; i < N; ++i) {if (visit[i] && p[i] == i) {res.push_back({i, cnt[i], estate[i], area[i]});}}sort(res.begin(), res.end());cout << res.size() << endl;for (auto &item:res) {int length = item.number;printf("%04d %d %.3lf %.3lf\n", item.id, item.number, item.estate * 1.0 / length, item.area * 1.0 / length);}return 0;
}

1118 Birds in Forest

AcWing链接
PAT链接

解析
在每幅图片的输入过程中,让所有的鸟都和第一只鸟的并查集合并,记录合并的次数
因为鸟的编号是递增的,所以用一个变量记录最大的编号就是鸟的总数
鸟的总数减去合并的次数(一次合并让两只鸟加入一个并查集中),就是树的个数(不同并查集的个数)

注意点

#include <iostream>using namespace std;
const int N = 10010;
int n, idx = 0, k;
int p[N], birds[N];int find(int x) {if (p[x] != x) p[x] = find(p[x]);return p[x];
}int main() {cin >> n;for (int i = 0; i < N; ++i) {p[i] = i;}int max_id = 1, cnt = 0;while (n--) {cin >> k;for (int i = 0; i < k; ++i) {cin >> birds[i];if (max_id < birds[i]) max_id = birds[i];}int pa = find(birds[0]);for (int i = 1; i < k; ++i) {int pb = find(birds[i]);if (pa != pb) {p[pb] = pa;cnt++;}}}cout << max_id - cnt << " " << max_id << endl;cin >> k;while (k--) {int a, b;cin >> a >> b;if (find(a) == find(b)) puts("Yes");else puts("No");}return 0;
}

模板

AcWing链接
PAT链接

英语单词

解析

注意点