首页 > 其他 > 详细

8.29 活着的意义

时间:2019-08-29 22:44:33      阅读:95      评论:0      收藏:0      [点我收藏+]

题意

给一张\(n\)个点\(m\)条边的无向图,有一个对于这个无向图的操作,即去除图中的一个生成森林(即所有连通块中生成树的集合)。不断对该无向图进行操作直到该图中的边全部被删除。对于每一条边,输出他是在第几次被删除的。

如果有多种方案,输出其中一种即可


解法

首先我们有一个很好想的\(O(MN)\)暴力

遍历每一条边,每次进行生成树操作:具体来说,就是每次开一个并查集,如果该边的两个端点不在同一个连通块中,则把它们联通,并且把该边从边集中删除;否则跳过该边

考虑我们如何对暴力算法进行优化

如果我们开若干个并查集,每次对于一条边,如果在\(1\)号并查集中它的两端所连接的点在一个连通块内,我们就在\(2\)号并查集中进行插入,以此类推...

通过上述算法,我们可以求出每一次操作后形成的生成森林

但是我们会发现,这个算法和原来相比,不仅时间复杂度没有改观,空间复杂度反而变得更劣了

但是这个算法的思想却有一定的启发性

我们可以发现一个性质:对于一条边,如果它可以在第\(i\)号并查集中插入,那么它也一定可以在\(i+1...n\)号并查集中插入

这个可以用反证法证明,也可以意会理解一下

发现了这个性质以后,我们就可以二分出第一个可以插入的并查集编号了

这样时间复杂度由\(O(MN)\)优化到了\(O(MlogM)\)

但是空间复杂度仍然无法承受。此时我们可以用哈希表优化空间

我们把若干个并查集排在一起,可以看做一个若干行\(n\)列的矩阵,把每个矩阵的坐标\((x,y)\)映射成某个数

如果我们把这个矩阵代表的位置全部开出来,需要\(M^2\)的空间

但实际上我们只有\(M\)条边,这个矩阵中有许多的空间是闲置的。考虑到每一条边会且仅会插入一个并查集,所以至多会有\(2M\)个不同的位置,并查集开\(2M\)的空间即可

将这个数插入哈希表,重新离散化即可

还有一个骚操作:用指针动态开点??!但是不太会用指针,就先咕着吧


代码

#include <cstdio>
#include <cstring>
#include <cctype>

using namespace std;

int read();

const int N = 2e6 + 10;
const int mod = 1048575;

int n, m, cnt;

struct UnionSet {
    int id[N << 1];
    
    void config() {
        for (int i = 1; i <= (m << 1); ++i) id[i] = i;
    }
    int get(int x) {
        return x == id[x] ? x : id[x] = get(id[x]); 
    }
    int merge(int x, int y) {
        x = get(x), y = get(y);
        return (x == y) ? 0 : (id[y] = x);
    }
} ufs;

struct HashMap {
    int cap;
    int head[N], nxt[N];
    long long to[N];
    
    void config() {
        cap = 0;
        memset(head, 0, sizeof head);
    }
    int insert(long long x) {
        int u = x & mod;
        to[++cap] = x, nxt[cap] = head[u], head[u] = cap;
        return cap;
    }
    int find(long long x) {
        int u = x & mod;
        for (int i = head[u]; i; i = nxt[i])
            if (to[i] == x) return i;
        return 0;   
    }
} mp;

inline long long gain(int x, int y) {
    return 1LL * (x - 1) * n + y;   
}

int check(int x, int u, int v) {
    int idu = mp.find((gain(x, u))), idv = mp.find(gain(x, v));
    if (!idu || !idv || (ufs.get(idu) ^ ufs.get(idv)))  return 1;
    return 0;
}

int search(int l, int r, int u, int v) {
    int res = 0;
    while (l <= r) {
        int mid = l + r >> 1;
        if (check(mid, u, v))   res = mid, r = mid - 1;
        else l = mid + 1;
    }
    return res;
}

int main() {
    
    n = read(), m = read();
    
    ufs.config();
    
    int u, v;
    for (int i = 1; i <= m; ++i) {
        u = read(), v = read();
        int can = search(1, cnt, u, v);
        if (!can) {
            can = ++cnt;
            ufs.merge(mp.insert(gain(cnt, u)), mp.insert(gain(cnt, v)));    
        } else {
            long long x = gain(can, u), y = gain(can, v);
            int idu = mp.find(x);
            int idv = mp.find(y);
            if (!idu)   idu = mp.insert(x);
            if (!idv)   idv = mp.insert(y);
            ufs.merge(idu, idv);
        }
        printf("%d\n", can);
    }
            
    return 0;
}

int read() {
    int x = 0, c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c))  x = x * 10 + c - 48, c = getchar();
    return x;   
}

8.29 活着的意义

原文:https://www.cnblogs.com/VeniVidiVici/p/11432037.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!