Union Findデータ構造を実装
大学院の授業で最小スパニング木をやって、その実装方法の途中でやったUnion Findを忘れないうちに実装。
美しいアルゴリズムを見ると本当にSUGEEEEEEEEEってなるよね。
#include <iostream> #include <vector> class UnionFind{ private: std::vector<int> data_array; const int root(int id){ if(data_array[id] >= 0) return data_array[id] = root(data_array[id]); else return id; } public: UnionFind(size_t size) : data_array(size,-1){} // unionは予約語 bool union_(int lhs, int rhs){ lhs = root(lhs); rhs = root(rhs); bool is_union = (lhs != rhs); if(is_union){ if( data_array[lhs] > data_array[rhs]){ std::swap(lhs,rhs); } data_array[lhs] += data_array[rhs]; data_array[rhs] = lhs; } return is_union; } bool find(int lhs, int rhs){ return ( root(lhs) == root(rhs) ); } };
書き終わってこれ以上綺麗にはならんだろ……とか思ってたら、
http://www.prefield.com/algorithm/container/union_find.htmlを見て絶望した。
綺麗すぎワロタ。