基于类实现并查集

小9

于 2019-02-15 15:42:30 发布

阅读量560

点赞数

分类专栏： ----------algo---------- 文章标签： c++ 并查集算法

本文链接：https://blog.csdn.net/zhengwei223/article/details/87365768

版权

----------algo---------- 专栏收录该内容

31 篇文章

订阅专栏

/*===并查集===*/
class Node {
public:
    Node *parent;

    Node() : parent(NULL) {}
};

Node *find(Node *x) {
    Node *p = x;
    if (p->parent == NULL)return p;
    set<Node *> path;
    while (p->parent != NULL) {
        path.insert(p);
        p = p->parent;
    }
//    优化，缩短路径，所有经过的父节点都变成最终父节点的直接儿子
    for (set<Node *>::iterator iter = path.begin(); iter != path.end(); ++iter) {
        (*iter)->parent = p;
    }
    return p;
}

void merge(Node *n1, Node *n2) {
    find(n2)->parent = find(n1);
}

/*===并查集  end===*/