并查集70TLE求调

cgxd @ 2024-08-10 18:06:18

#include<bits/stdc++.h>
using namespace std;
int n, m, f[1000005];
bitset<1005> bs[1005];
int id(int i, int j){
    return (i - 1) * n + j;
}int find(int x){
    return f[x] == x? x: f[x] = find(f[x]);
}void uni(int x, int y){
    f[find(x)] = find(y);
}signed main(){
    scanf("%d%d", &n, &m);
    iota(f, f + n * n + 1, 0);
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            int k;
            scanf("%1d", &k);
            bool bl = k;
            bs[i][j] = bl;
        }
    }for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            if(i != n and (bs[i][j] xor bs[i + 1][j]))
                uni(id(i, j), id(i + 1, j));
            if(j != n and (bs[i][j] xor bs[i][j + 1]))
                uni(id(i, j), id(i, j + 1));
        }
    }while(m--){
        int x, y, cnt = 0;
        scanf("%d%d", &x, &y);
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= n; ++j)
                cnt += find(id(x, y)) == find(id(i, j));
        }printf("%d\n", cnt);
    }return 0;
}

by Causality_ @ 2024-08-16 11:25:26

@cgxd 方法有点复杂，可以读到迷宫之后直接bfs全部，全部存下来，然后询问的时候直接调用，还有就是第三个测试点是n=1000，m=100000，不知道为什么我的1005和100005就wa，建议改成1010和100010

by Causality_ @ 2024-08-16 11:36:50

然后如果一定要用并查集的话可以看看题解第一面最后一个

by Causality_ @ 2024-08-16 11:38:01

不好意思瞎了，那个不是并查集，我看到并查集就以为是了。。。。。。

by Nail9 @ 2024-08-22 21:14:13

@cgxd 在每次查询操作时，上述代码都会把整个数组遍历一遍。查询操作共有 1\times 10^5 次，因此这部分的时间复杂度就达到了 O(mn^2) = O(1\times 10^{11})，肯定会超时。

可以先记录每个连通块的元素数量，最后输出所在连通块的数量即可，不用遍历整个表格。

by Nail9 @ 2024-08-22 21:14:53

@cgxd 改自你的代码，实测 AC：

#include<bits/stdc++.h>
using namespace std;
int n, m, f[1000005];
bitset<1005> bs[1005];
int ans[1000005];
int id(int i, int j){
    return (i - 1) * n + j;
}int find(int x){
    return f[x] == x? x: f[x] = find(f[x]);
}void uni(int x, int y){
    f[find(x)] = find(y);
}signed main(){
    scanf("%d%d", &n, &m);
    // iota(f, f + n * n + 1, 0);
    for(int i = 1; i <= 1000000; ++i) f[i] = i;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            int k;
            scanf("%1d", &k);
            bool bl = k;
            bs[i][j] = bl;
        }
    }for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            if(i != n and (bs[i][j] xor bs[i + 1][j]))
                uni(id(i, j), id(i + 1, j));
            if(j != n and (bs[i][j] xor bs[i][j + 1]))
                uni(id(i, j), id(i, j + 1));
        }
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            ++ans[find(id(i, j))];
    while(m--){
        int x, y, cnt = 0;
        scanf("%d%d", &x, &y);
        printf("%d\n", ans[find(id(x, y))]);
    }
    return 0;
}

by cgxd @ 2024-08-22 21:38:37

@Nail9 已过，已关