CQY的图形屋

用递归的思路写的并查集, 觉得更容易理解, 虽然此处并没有针对每一个小集合的大小进行优化, 算法执行过程当中有可能会导致某一个集合变得很大:

unordered_map<int, int> f;

int find(int x) {
    if (!f.count(x)) f[x] = x;
    if (x != f[x]) f[x] = find(f[x]);
    return f[x];
}

void uni(int x, int y) {
    x = find(x), y = find(y);
    if (x != y) f[x] = y;
}

大年初一的, 复习了一下并查集, 用的教材上面写的并查集实际上用起来总感觉很别扭, 比如索引不是从0开始, 没有对处于同一集合内的元素作判断, 以及用了树作为存储集合根结点的数据结构, 于是便自己写了个C++版的.

继续阅读C++版并查集