标签扩展域并查集下的文章 - xiaoeyv Blog

登录

找到 2 篇与扩展域并查集相关的结果

【洛谷】P2024 [NOI2001] 食物链

【洛谷】P2024 [NOI2001] 食物链题目链接：[P2024 [NOI2001] 食物链](https://www.luogu.com.cn/problem/P2024) 思路本题可以使用“扩展域并查集”的方法来解决，即把每个节点拆成三种角色（本体、吃的、被吃的）来模拟三种关系。也可以使用“带权并查集”方法，通过设置每个节点到其父节点的相对关系来处理三种状态。代码扩展域并查集 #define maxn 50010 #define maxm 100010 #include<bits/stdc++.h> using namespace std; int n, k; int pre[maxn * 3], r[maxn * 3]; int ans = 0; int find(int x) { return x == pre[x] ? x : pre[x] = find(pre[x]); } bool join(int x, int y) { int rx = find(x), ry = find(y); if (rx == ry) { return false; } if (r[rx] < r[ry]) pre[rx] = ry; else { pre[ry] = rx; if (r[rx] == r[ry]) r[rx]++; } return true; } int main() { cin >> n >> k; for (int i = 1; i <= n * 3; i++) pre[i] = i; while (k--) { int opt, x, y; cin >> opt >> x >> y; if (x > n || y > n) { ans++; } else if (opt == 1) { if (find(x) == find(y + n) || find(x) == find(y + n + n)) { ans++; continue; } join(x, y); join(x + n, y + n); join(x + n + n, y + n + n); } else { if (x == y || find(x) == find(y) || find(x) == find(y + n + n)) { ans++; continue; } join(x, y + n); join(x + n, y + n + n); join(x + n + n, y); } } cout << ans << endl; } 带权并查集 #define maxn 50010 #define maxm 100010 #include<bits/stdc++.h> using namespace std; int n, k; int pre[maxn], sz[maxn]; int find(int x) { if (pre[x] != x) { int fa = pre[x]; pre[x] = find(pre[x]); sz[x] = (sz[fa] + sz[x]) % 3; } return pre[x]; } bool join(int x, int y, int w) { int rx = find(x), ry = find(y); if (rx == ry) return (sz[x] - sz[y] + 3) % 3 == w; pre[rx] = ry; sz[rx] = (sz[y] - sz[x] + w + 3) % 3; return true; } int ans = 0; int main() { cin >> n >> k; for (int i = 1; i <= n; i++) pre[i] = i; for (int i = 1; i <= k; i++) { int opt, x, y; cin >> opt >> x >> y; if (x > n || y > n) ans++; else if (opt == 1) { if (!join(x, y, 0)) { ans++; } } else { if (x == y || !join(x, y, 1)) { ans++; } } } cout << ans << endl; return 0; }

C++# C++# 并查集 # 扩展域并查集 # 洛谷 # 带权并查集 # NOI

xiaoeyv 1年前

0 9 0

【洛谷】P1892 [BalticOI 2003] 团伙

【洛谷】P1892 [BalticOI 2003] 团伙题目链接：[P1892 [BalticOI 2003] 团伙](https://www.luogu.com.cn/problem/P1892) 思路除了并查集外，还要记录每个人之间的关系，典型的扩展域并查集模板题。代码写的时候用了秩优化，能优化一些效率。 // // Created by xiaoeyv on 2025/6/19. // #define maxn 1010 #define maxm 5010 #include<bits/stdc++.h> using namespace std; int n, m; int pre[maxn * 2], r[maxn * 2]; int find(int x) { return pre[x] == x ? x : pre[x] = find(pre[x]); } void join(int x, int y) { int rx = find(x), ry = find(y); if (rx == ry) return; if (r[rx] < r[ry]) pre[rx] = ry; else { pre[ry] = rx; if (r[rx] == r[ry]) r[rx]++; } } int main() { cin >> n >> m; memset(r, 0, sizeof(r)); for (int i = 1; i <= n * 2; i++) { pre[i] = i; } for (int i = 1; i <= m; i++) { char op; int p, q; cin >> op >> p >> q; if (op == 'F') { join(p, q); } else { join(p + n, q); join(p, q + n); } } set<int> ans; for (int i = 1; i <= n; i++) { ans.insert(find(i)); } cout << ans.size() << endl; return 0; }

C++# C++# 并查集 # 扩展域并查集 # BalticOI # 洛谷 # 秩

xiaoeyv 1年前

0 4 0