union_find.h

#pragma once
 
#include <vector>
 
namespace cgv {
        namespace data {
 
struct union_find : public std::vector<unsigned int>
{
        union_find(unsigned int n) { init(n); }
        void init(unsigned int n) { 
                resize(n); 
                for (unsigned int i=0; i<n; ++i) 
                        at(i) = i; 
        }
        unsigned int find(unsigned int i)
        {
                // find representative j
                unsigned int j = i;
                while (at(j) != j)
                        j = at(j);
                // compress path
                while (i != j) {
                        unsigned int tmp = at(i);
                        at(i) = j;
                        i = tmp;
                }
                return j;
        }
        void unify(unsigned int i, unsigned int j)
        {
                at(find(i)) = j;
        }
};
 
        }
}