不相交集数据结构：每棵树的轨迹大小

Question

下面是我跟踪不相交集合森林中每棵树的大小的实现。

你能告诉我它有什么问题吗？我正在尝试解决 UVa 问题 https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3638

#include <iostream>
#include <cstdio>
#include <unordered_map>
using namespace std;

class Node {
    public :
    int id;
    Node *parent;
    unsigned long long rank;



    Node(int id) {
        this->id = id;
       // this->data = data;
        this->rank =1; //size here
        this->parent = this;
    }
    friend class DisjointSet;
};

  class DisjointSet {
    unordered_map<int,Node*> nodesMap;

    Node *find_set_helper(Node *aNode) {

        if (aNode == aNode->parent) {
            return aNode->parent;
        }
        return find_set_helper(aNode->parent);
    }

    void link(Node *xNode,Node *yNode) {
        if( xNode->rank > yNode->rank) {
            yNode->parent = xNode;
            xNode->rank += yNode->rank;
        }
        // else if(xNode-> rank < yNode->rank){
        //     xNode->parent = yNode;
        //     yNode->rank += xNode->rank;
        // }
        else {
            xNode->parent = yNode;
            yNode->rank += xNode->rank;
        }
    }
public:
    DisjointSet() {

    }

    void AddElements(int sz) {
        for(int i=0;i<sz;i++)
            this->make_set(i);
    }

    void make_set(int id) {
        Node *aNode = new Node(id);
        this->nodesMap.insert(make_pair(id,aNode));
    }

    void Union(int xId, int yId) {
        Node *xNode = find_set(xId);
        Node *yNode = find_set(yId);

        if(xNode && yNode)
          link(xNode,yNode);
    }

    Node* find_set(int id) {
      unordered_map<int,Node*> :: iterator itr = this->nodesMap.find(id);
      if(itr == this->nodesMap.end())
          return NULL;

      return this->find_set_helper(itr->second);
    }



    ~DisjointSet(){
        unordered_map<int,Node*>::iterator itr;
        for(itr = nodesMap.begin(); itr != nodesMap.end(); itr++) {
            delete (itr->second);
        }
    }

};
int main() {

    int n,m,k,first,cur;

    //freopen("in.in","r",stdin);

    scanf("%d %d",&n,&m);

    while(n != 0 || m != 0) {

        DisjointSet *ds = new DisjointSet();
        ds->AddElements(n); // 0 to n-1

        //printf("\n n = %d m = %d",n,m);


        for(int i=1;i<=m;i++) {
            scanf("%d",&k);
            //printf("\nk=%d",k);
            if ( k > 0 ) {

                scanf("%d",&first);
                for(int j=2;j<=k;j++) {
                    scanf("%d",&cur);
                    ds->Union(first,cur);
                }
            }
        }

        Node *zeroSet = ds->find_set(0);
       // unsigned long long count = ds->getCount(zeroSet->id);
        printf("%llu\n",zeroSet->rank);
        delete ds;

        scanf("%d %d",&n,&m);
    }

    return 0;
}

上面代码中的 link 函数完成更新树大小的工作。

问题的解决方法是找到元素0所属的集合，并得到集合中代表元素的大小。但是我用这段代码得到了错误的答案。

你能帮帮我吗

Answer 1

在你的 Union 函数中，检查两个节点是否已经在同一个集合中。

if(xNode && yNode && xNode != yNode)
      link(xNode,yNode);

不相交集数据结构：每棵树的轨迹大小

Disjoint set data structure : track size of each tree

c++

algorithm

data-structures

disjoint-sets

disjoint-union