找到
5
篇与
并查集
相关的结果
-
C++求联通块数量 本文使用了下面五种方法求联通块数量： 并查集 深度优先搜索DFS 广度优先搜索BFS Floyd Kruskal #include<bits/stdc++.h> using namespace std; const int N = 110; const int M = 10010; int n, m; vector<int> g[N]; int ans = 0; // 1.并查集 int pre[N]; int find ( int x ) { return x == pre[x] ? pre[x] : pre[x] = find ( pre[x] ); } void merge ( int x, int y ) { int rx = find ( x ), ry = find ( y ); if ( rx != ry ) { pre[rx] = ry; } } void solveA() { for ( int i = 1; i <= n; i++ ) { pre[i] = i; } for ( int i = 1; i <= m; i++ ) { int u, v; cin >> u >> v; g[u].emplace_back ( v ); g[v].emplace_back ( u ); merge ( u, v ); } for ( int i = 1; i <= n; i++ ) { if ( pre[i] == i ) { ans++; } } cout << ans; } // 2.深搜 int vis[N]; void dfs ( int x ) { for ( auto &u : g[x] ) { if ( vis[u] ) { continue; } vis[u] = true; dfs ( u ); } } void solveB() { for ( int i = 1; i <= m; i++ ) { int u, v; cin >> u >> v; g[u].emplace_back ( v ); g[v].emplace_back ( u ); } for ( int i = 1; i <= n; i++ ) { if ( !vis[i] ) { dfs ( i ); ans++; } } cout << ans; } // 3.广搜 void bfs ( int x ) { queue<int> q; q.emplace ( x ); while ( !q.empty() ) { int u = q.front(); q.pop(); for ( auto &v : g[u] ) { if ( vis[v] ) { continue; } vis[v] = true; q.emplace ( v ); } } } void solveC() { for ( int i = 1; i <= m; i++ ) { int u, v; cin >> u >> v; g[u].emplace_back ( v ); g[v].emplace_back ( u ); } for ( int i = 1; i <= n; i++ ) { if ( !vis[i] ) { bfs ( i ); ans++; } } cout << ans; } // 4.Floyd int adj[N][N]; void solveD() { for ( int i = 1; i <= n; i++ ) { adj[i][i] = 1; } for ( int i = 1; i <= m; i++ ) { int u, v; cin >> u >> v; adj[u][v] = adj[v][u] = 1; } ans = 0; for ( int k = 1; k <= n; k++ ) { for ( int i = 1; i <= n; i++ ) { for ( int j = 1; j <= n; j++ ) { if ( adj[i][k] && adj[k][j] ) { adj[i][j] = 1; } } } } for ( int i = 1; i <= n; i++ ) { if ( !vis[i] ) { ans++; for ( int j = 1; j <= n; j++ ) { if ( adj[i][j] ) { vis[j] = true; } } } } cout << ans; } // 5.Kruskal 最小生成森林 struct Edge { int u, v; } e[M]; void solveE() { for ( int i = 1; i <= n; i++ ) { pre[i] = i; } for ( int i = 1; i <= m; i++ ) { int u, v; cin >> u >> v; e[i] = {u, v}; } ans = n; for ( int i = 1; i <= m; i++ ) { int u = e[i].u, v = e[i].v; int ru = find ( u ), rv = find ( v ); if ( ru != rv ) { merge ( ru, rv ); ans--; } } cout << ans; } // int main() { cin >> n >> m; // solveA(); // solveB(); // solveC(); // solveD(); solveE(); return 0; }
-
【洛谷】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; }
-
【洛谷】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; }
-
【洛谷】P2820 局域网 题目链接：P2820 局域网 - 洛谷 题目简述 去除 $k$ 个边中的最大回路边。 思路 在输入的时候统计权重总和，减去最小生成树的总和。 这道题用简单数组实现 Prim，复杂度是 $O(n^2)$； 用堆优化的 Prim 是 $O(k\log n)$； Kruskal 则是 $O(k\log k)\approx O(k\log n)$。 在本题规模下（$n\le100$、最坏 $k\approx4950$），这两种算法都可以解决，但Kruskal+并查集更加直观简洁。 代码 // // Created by xiaoeyv on 2025/6/19. // #define maxn 110 #define maxm (maxn * (maxn-1))/2 #include<bits/stdc++.h> using namespace std; int pre[maxn], r[maxn], sz[maxn]; bool vis[maxn]; int n, k; int cnt = 0; int ans = 0; struct Edge { int u, v, w; } e[maxm]; int find(int x) { return pre[x] == x ? 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 >> k; memset(r, 0, sizeof(r)); memset(sz, 0, sizeof(sz)); for (int i = 0; i <= n; i++) pre[i] = i; for (int i = 1; i <= k; i++) { int u, v, w; cin >> u >> v >> w; ans += w; e[i].u = u, e[i].v = v, e[i].w = w; } sort(e + 1, e + k + 1, [](const auto &x, const auto &y) { return x.w < y.w; }); for (int i = 1; i <= k && cnt < n - 1; i++) { int u = e[i].u, v = e[i].v, w = e[i].w; int ru = find(u), rv = find(v); if (ru != rv) { join(u, v); ans -= w; cnt++; } } cout << ans << endl; return 0; }
-
【洛谷】P2078 朋友 题目链接：P2078 朋友 - 洛谷 思路 这道题思路很简单，建立A公司和B公司的并查集，遍历小明认识的人ans1和小红认识的人ansB，然后输出min(ansA, ansB)即可 代码 // // Created by xiaoeyv on 2025/6/18. // #define maxn 10010 #include<bits/stdc++.h> using namespace std; int n, m, p, q; int preA[maxn], rA[maxn], preB[maxn], rB[maxn]; int find(int x, int *pre) { return pre[x] == x ? x : pre[x] = find(pre[x], pre); } void join(int x, int y, int *pre, int *r) { int rx = find(x, pre), ry = find(y, pre); if (rx == ry) return; if (r[rx] < r[ry]) pre[rx] = ry; else { pre[ry] = rx; if (r[rx] == r[ry]) r[rx]++; } } int ansA = 0, ansB = 0; int main() { cin >> n >> m >> p >> q; // init for (int i = 0; i <= n; i++) { preA[i] = i; } for (int i = 0; i <= m; i++) { preB[i] = i; } memset(rA, 0, sizeof(rA)); memset(rB, 0, sizeof(rB)); while (p--) { int x, y; cin >> x >> y; join(x, y, preA, rA); } while (q--) { int x, y; cin >> x >> y; join(-x, -y, preB, rB); } int rootA = find(1, preA); int rootB = find(1, preB); for (int i = 1; i <= n; i++) if (find(i, preA) == rootA) ansA++; for (int i = 1; i <= m; i++) if (find(i, preB) == rootB) ansB++; cout << min(ansA, ansB) << endl; return 0; }
![【洛谷】P2024 [NOI2001] 食物链](http://blog.xiaoeyv.com/usr/themes/joe/assets/images/thumb/32.jpg)
![【洛谷】P1892 [BalticOI 2003] 团伙](http://blog.xiaoeyv.com/usr/themes/joe/assets/images/thumb/24.jpg)
