[已解决]蒟蒻再次求助！！

元豪

O2优化 , 常数优化都弄了，还是过不了

哪位dalao帮忙优化一下效率啊

1. /* https://www.luogu.com.cn/problem/P1536 -- 村村通 */
   
2. 
   
3. /*  */
   
4. 
   
5. #include <bits/stdc++.h>
   
6. using namespace std;
   
7. 
   
8. map <int, int> g;
   
9. int n, m, a, b, c, d;
   
10. 
    
11. int find(int a){
    
12.     if (g[a] == a){
    
13.         return a;
    
14.     }
    
15.     else{
    
16.         return find(g[a]);
    
17.     }
    
18. }
    
19. 
    
20. int main(){
    
21.     freopen("Input.in", "r", stdin);
    
22.     while (true){
    
23.         int ans = 0;
    
24.         scanf("%d", &a);
    
25.         if (a == 0) break;
    
26.         for (int i = 0; i < a; i++) g[i + 1] = i + 1;
    
27.         scanf("%d", &b);
    
28.         for (int i = 0; i < b; i++){
    
29.             scanf("%d%d", &c, &d);
    
30.             g[find(c)] = find(d);
    
31.         }
    
32.         for (int i = 0; i < a; i++){
    
33.             if (find(i + 1) == i + 1){
    
34.                 ans++;
    
35.             }
    
36.         }
    
37.         printf("%d\n", ans - 1);
    
38.     }
    
39. 
    
40.     return 0;
    
41. }

复制代码

最佳答案

月排行榜 / 总排行榜

陶远航

2023-5-3 15:24:50

这段代码中使用了递归的方式进行 find 操作，可能会导致栈空间过度消耗。建议使用循环代替递归。

另外，map 会增加常数开销，建议考虑使用数组代替 map 存储并查集。

下面是优化后的代码示例，希望对您有所帮助：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. const int MAXN = 100005;
   
5. int fa[MAXN];
   
6. 
   
7. int find(int x) {
   
8.     if (fa[x] == x) return x;
   
9.     return fa[x] = find(fa[x]);
   
10. }
    
11. 
    
12. int main() {
    
13.     int n, m, a, b, c, d;
    
14.     while (true) {
    
15.         scanf("%d", &n);
    
16.         if (n == 0) break;
    
17.         for (int i = 1; i <= n; i++) fa[i] = i;
    
18.         scanf("%d", &m);
    
19.         for (int i = 0; i < m; i++) {
    
20.             scanf("%d%d", &a, &b);
    
21.             fa[find(a)] = find(b);
    
22.         }
    
23.         int ans = 0;
    
24.         for (int i = 1; i <= n; i++) {
    
25.             if (fa[i] == i) ans++;
    
26.         }
    
27.         printf("%d\n", ans - 1);
    
28.     }
    
29.     return 0;
    
30. }
    

复制代码

跳转到最佳答案楼层

元豪

代码里有题目链接

元豪

@isdkz

陶远航

这段代码中使用了递归的方式进行 find 操作，可能会导致栈空间过度消耗。建议使用循环代替递归。

另外，map 会增加常数开销，建议考虑使用数组代替 map 存储并查集。

下面是优化后的代码示例，希望对您有所帮助：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. const int MAXN = 100005;
   
5. int fa[MAXN];
   
6. 
   
7. int find(int x) {
   
8.     if (fa[x] == x) return x;
   
9.     return fa[x] = find(fa[x]);
   
10. }
    
11. 
    
12. int main() {
    
13.     int n, m, a, b, c, d;
    
14.     while (true) {
    
15.         scanf("%d", &n);
    
16.         if (n == 0) break;
    
17.         for (int i = 1; i <= n; i++) fa[i] = i;
    
18.         scanf("%d", &m);
    
19.         for (int i = 0; i < m; i++) {
    
20.             scanf("%d%d", &a, &b);
    
21.             fa[find(a)] = find(b);
    
22.         }
    
23.         int ans = 0;
    
24.         for (int i = 1; i <= n; i++) {
    
25.             if (fa[i] == i) ans++;
    
26.         }
    
27.         printf("%d\n", ans - 1);
    
28.     }
    
29.     return 0;
    
30. }
    

复制代码

元豪

陶远航 发表于 2023-5-3 15:24
这段代码中使用了递归的方式进行 find 操作，可能会导致栈空间过度消耗。建议使用循环代替递归。

另外， ...

哦，原来是map有问题

感谢大佬

歌者文明清理员

元豪 发表于 2023-5-3 15:26
哦，原来是map有问题

感谢大佬

下面是完整的 C++ 代码实现，主要使用了 Kruskal 算法。

时间复杂度为 O(mlogm)，其中 m 是边数。
下面是完整的 C++ 代码实现：

cpp

1. #include <iostream>
   
2. #include <cstdio>
   
3. #include <algorithm>
   
4. 
   
5. using namespace std;
   
6. 
   
7. const int MAXN = 100010;
   
8. const int MAXM = 200010;
   
9. 
   
10. int n, m;
    
11. int p[MAXN], rank[MAXN];
    
12. 
    
13. struct Edge {
    
14.     int u, v, w;
    
15. } e[MAXM];
    
16. 
    
17. bool cmp(const Edge& a, const Edge& b) {
    
18.     return a.w < b.w;
    
19. }
    
20. 
    
21. int find(int x) {
    
22.     if (x != p[x]) p[x] = find(p[x]);
    
23.     return p[x];
    
24. }
    
25. 
    
26. void unite(int x, int y) {
    
27.     x = find(x), y = find(y);
    
28.     if (x == y) return;
    
29.     if (rank[x] < rank[y]) swap(x, y);
    
30.     p[y] = x;
    
31.     if (rank[x] == rank[y]) ++rank[x];
    
32. }
    
33. 
    
34. int kruskal() {
    
35.     sort(e, e + m, cmp);
    
36.     for (int i = 1; i <= n; ++i) {
    
37.         p[i] = i;
    
38.         rank[i] = 0;
    
39.     }
    
40.     int res = 0, cnt = 0;
    
41.     for (int i = 0; i < m; ++i) {
    
42.         if (cnt == n - 1) break;
    
43.         int u = e[i].u, v = e[i].v, w = e[i].w;
    
44.         if (find(u) == find(v)) continue;
    
45.         unite(u, v);
    
46.         res += w;
    
47.         ++cnt;
    
48.     }
    
49.     return res;
    
50. }
    
51. 
    
52. int main() {
    
53.     scanf("%d%d", &n, &m);
    
54.     for (int i = 0; i < m; ++i) {
    
55.         int u, v, w;
    
56.         scanf("%d%d%d", &u, &v, &w);
    
57.         e[i] = {u, v, w};
    
58.     }
    
59.     printf("%d\n", kruskal());
    
60.     return 0;
    
61. }

复制代码

isdkz

元豪 发表于 2023-5-3 15:24
@isdkz

来晚了

元豪

isdkz 发表于 2023-5-3 15:33
来晚了

sfqxx

妈呀，陶远航

元豪

sfqxx 发表于 2023-5-3 15:57
妈呀，陶远航

他在我发表1分钟后就回复了