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

元豪

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

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

/* https://www.luogu.com.cn/problem/P1536 -- 村村通 */

/*  */

#include <bits/stdc++.h>
using namespace std;

map <int, int> g;
int n, m, a, b, c, d;

int find(int a){
    if (g[a] == a){
        return a;
    }
    else{
        return find(g[a]);
    }
}

int main(){
    freopen("Input.in", "r", stdin);
    while (true){
        int ans = 0;
        scanf("%d", &a);
        if (a == 0) break;
        for (int i = 0; i < a; i++) g[i + 1] = i + 1;
        scanf("%d", &b);
        for (int i = 0; i < b; i++){
            scanf("%d%d", &c, &d);
            g[find(c)] = find(d);
        }
        for (int i = 0; i < a; i++){
            if (find(i + 1) == i + 1){
                ans++;
            }
        }
        printf("%d\n", ans - 1);
    }

    return 0;
}

最佳答案

月排行榜 / 总排行榜

陶远航

2023-5-3 15:24:50

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

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

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

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int fa[MAXN];

int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

int main() {
    int n, m, a, b, c, d;
    while (true) {
        scanf("%d", &n);
        if (n == 0) break;
        for (int i = 1; i <= n; i++) fa[i] = i;
        scanf("%d", &m);
        for (int i = 0; i < m; i++) {
            scanf("%d%d", &a, &b);
            fa[find(a)] = find(b);
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (fa[i] == i) ans++;
        }
        printf("%d\n", ans - 1);
    }
    return 0;
}

跳转到最佳答案楼层

元豪

代码里有题目链接

元豪

@isdkz

陶远航

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

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

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

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int fa[MAXN];

int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

int main() {
    int n, m, a, b, c, d;
    while (true) {
        scanf("%d", &n);
        if (n == 0) break;
        for (int i = 1; i <= n; i++) fa[i] = i;
        scanf("%d", &m);
        for (int i = 0; i < m; i++) {
            scanf("%d%d", &a, &b);
            fa[find(a)] = find(b);
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (fa[i] == i) ans++;
        }
        printf("%d\n", ans - 1);
    }
    return 0;
}

元豪

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

另外， ...

哦，原来是map有问题

感谢大佬

歌者文明清理员

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

感谢大佬

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

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

cpp

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 100010;
const int MAXM = 200010;

int n, m;
int p[MAXN], rank[MAXN];

struct Edge {
    int u, v, w;
} e[MAXM];

bool cmp(const Edge& a, const Edge& b) {
    return a.w < b.w;
}

int find(int x) {
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}

void unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (rank[x] < rank[y]) swap(x, y);
    p[y] = x;
    if (rank[x] == rank[y]) ++rank[x];
}

int kruskal() {
    sort(e, e + m, cmp);
    for (int i = 1; i <= n; ++i) {
        p[i] = i;
        rank[i] = 0;
    }
    int res = 0, cnt = 0;
    for (int i = 0; i < m; ++i) {
        if (cnt == n - 1) break;
        int u = e[i].u, v = e[i].v, w = e[i].w;
        if (find(u) == find(v)) continue;
        unite(u, v);
        res += w;
        ++cnt;
    }
    return res;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        e[i] = {u, v, w};
    }
    printf("%d\n", kruskal());
    return 0;
}

isdkz

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

来晚了

元豪

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

sfqxx

妈呀，陶远航

元豪

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

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