134 lines
3.5 KiB
C++
134 lines
3.5 KiB
C++
#include <algorithm>
|
|
#include <iostream>
|
|
#include <unordered_map>
|
|
#include <unordered_set>
|
|
#include <vector>
|
|
|
|
using namespace std;
|
|
|
|
// Consolidation using a brute force approach
|
|
void SimpleConsolidate(vector<unordered_set<char>>& sets)
|
|
{
|
|
// Loop through the sets in reverse and consolidate them
|
|
for(auto last = sets.rbegin(); last != sets.rend(); ++last)
|
|
for(auto other = last + 1; other != sets.rend(); ++other)
|
|
{
|
|
bool hasIntersection = any_of(last->begin(), last->end(),
|
|
[&](auto val)
|
|
{ return other->contains(val); });
|
|
if(hasIntersection)
|
|
{
|
|
other->merge(*last);
|
|
sets.pop_back();
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
|
|
// As a second approach, use the connected-component-finding-algorithm
|
|
// from the C# entry to consolidate
|
|
struct Node
|
|
{
|
|
char Value;
|
|
Node* Parent = nullptr;
|
|
};
|
|
|
|
Node* FindTop(Node& node)
|
|
{
|
|
auto top = &node;
|
|
while (top != top->Parent) top = top->Parent;
|
|
for(auto element = &node; element->Parent != top; )
|
|
{
|
|
// Point the elements to top to make it faster for the next time
|
|
auto parent = element->Parent;
|
|
element->Parent = top;
|
|
element = parent;
|
|
}
|
|
return top;
|
|
}
|
|
|
|
vector<unordered_set<char>> FastConsolidate(const vector<unordered_set<char>>& sets)
|
|
{
|
|
unordered_map<char, Node> elements;
|
|
for(auto& set : sets)
|
|
{
|
|
Node* top = nullptr;
|
|
for(auto val : set)
|
|
{
|
|
auto itr = elements.find(val);
|
|
if(itr == elements.end())
|
|
{
|
|
// A new value has been found
|
|
auto& ref = elements[val] = Node{val, nullptr};
|
|
if(!top) top = &ref;
|
|
ref.Parent = top;
|
|
}
|
|
else
|
|
{
|
|
auto newTop = FindTop(itr->second);
|
|
if(top)
|
|
{
|
|
top->Parent = newTop;
|
|
itr->second.Parent = newTop;
|
|
}
|
|
else
|
|
{
|
|
top = newTop;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
unordered_map<char, unordered_set<char>> groupedByTop;
|
|
for(auto& e : elements)
|
|
{
|
|
auto& element = e.second;
|
|
groupedByTop[FindTop(element)->Value].insert(element.Value);
|
|
}
|
|
|
|
vector<unordered_set<char>> ret;
|
|
for(auto& itr : groupedByTop)
|
|
{
|
|
ret.push_back(move(itr.second));
|
|
}
|
|
|
|
return ret;
|
|
}
|
|
|
|
void PrintSets(const vector<unordered_set<char>>& sets)
|
|
{
|
|
for(const auto& set : sets)
|
|
{
|
|
cout << "{ ";
|
|
for(auto value : set){cout << value << " ";}
|
|
cout << "} ";
|
|
}
|
|
cout << "\n";
|
|
}
|
|
|
|
int main()
|
|
{
|
|
const unordered_set<char> AB{'A', 'B'}, CD{'C', 'D'}, DB{'D', 'B'},
|
|
HIJ{'H', 'I', 'K'}, FGH{'F', 'G', 'H'};
|
|
|
|
vector <unordered_set<char>> AB_CD {AB, CD};
|
|
vector <unordered_set<char>> AB_DB {AB, DB};
|
|
vector <unordered_set<char>> AB_CD_DB {AB, CD, DB};
|
|
vector <unordered_set<char>> HIJ_AB_CD_DB_FGH {HIJ, AB, CD, DB, FGH};
|
|
|
|
PrintSets(FastConsolidate(AB_CD));
|
|
PrintSets(FastConsolidate(AB_DB));
|
|
PrintSets(FastConsolidate(AB_CD_DB));
|
|
PrintSets(FastConsolidate(HIJ_AB_CD_DB_FGH));
|
|
|
|
SimpleConsolidate(AB_CD);
|
|
SimpleConsolidate(AB_DB);
|
|
SimpleConsolidate(AB_CD_DB);
|
|
SimpleConsolidate(HIJ_AB_CD_DB_FGH);
|
|
|
|
PrintSets(AB_CD);
|
|
PrintSets(AB_DB);
|
|
PrintSets(AB_CD_DB);
|
|
PrintSets(HIJ_AB_CD_DB_FGH);
|
|
}
|