UnionFind.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/basic.h>
 
#include <vector>
 
namespace ogdf {
namespace internal {
namespace gcm {
namespace datastructure {
 
class UnionFind {
private:
    std::vector<int> data;
 
public:
    UnionFind(unsigned int max_element) : data(max_element) { all_to_singletons(); }
 
    void all_to_singletons() { data.assign(data.size(), -1); }
 
    unsigned int find(unsigned int u) {
        OGDF_ASSERT(u < data.size());
        if (data[u] >= 0) {
            data[u] = find(data[u]);
            return data[u];
        } else {
            return u;
        }
    }
 
    unsigned int operator[](unsigned int u) { return find(u); }
 
    void merge(unsigned int u, unsigned int v) {
        unsigned int set_u = find(u);
        unsigned int set_v = find(v);
        if (set_u == set_v) {
            return;
        }
 
        if (data[set_u] > data[set_v]) {
            data[set_u] = set_v;
        } else if (data[set_v] > data[set_u]) {
            data[set_v] = set_u;
        } else {
            data[set_u] = set_v;
            --data[set_v];
        }
    }
};
}
}
}
}