Несвязанная структура данных набора: размер дорожки каждого дерева

Ниже моя реализация для отслеживания размера каждого дерева в непересекающемся множестве леса.

Подскажите, пожалуйста, что с ним не так? Я пытаюсь решить проблему UVa https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid = 8&страница = show_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;
}

Функция ссылки в приведенном выше коде выполняет работу по обновлению размера дерева.

Решение проблемы состоит в том, чтобы найти множество, к которому относятся элементы 0, и получить размер репрезентативного элемента множества.
Но я получаю неправильный ответ с этим кодом.

Не могли бы вы мне помочь

-2

Решение

В вашем Union функция, проверьте, находятся ли оба узла в одном наборе.

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

Другие решения


По вопросам рекламы ammmcru@yandex.ru
Adblock
detector