// -*- C++ -*- // /* Union-Find structure * Ehhez nagyon fontos, hogy az atadott property map inicializalva legyen * minden szobajovo kulcs ertekre, -1 -es ertekkel! */ #ifndef UNION_FIND_H #define UNION_FIND_H #include //#include namespace hugo { template class UnionFind { KeyIntMap& pointmap; struct VectorElementType { int boss; int count; VectorElementType(int _boss, int _count){ boss = _boss; count = _count; } }; std::vector container; public: UnionFind(KeyIntMap& _pointmap): pointmap(_pointmap){ } //Give a component of one point to the structure int addPoint(KeyType u){ int _index = container.size(); VectorElementType buf(_index,1); container.push_back(buf); return _index; } //Finds the big boss of u int find(KeyType u){ if (pointmap.get(u)==-1){ int whoami = addPoint(u); pointmap.set(u, whoami); return whoami; } else{ int emp = pointmap.get(u); int boss = container[emp].boss; while(emp != boss){ emp = boss; boss = container[emp].boss; } return boss; } } //Finds u and v in the structures and merges the comopnents, if not equal bool findAndMerge(KeyType u,KeyType v){ int bu = find(u); int bv = find(v); if (bu != bv){ unio(bu,bv); return true; } else{ return false; } } //Merges a into b void mergeInto(int a, int b){ container[a].boss = b; container[b].count += container[a].count; } //Makes the union void unio(int b1, int b2){ if (container[b1].count>container[b2].count){ mergeInto(b2,b1); } else{ mergeInto(b1,b2); } }//unio }; }//namespace hugo #endif