Program Listing for File UnionFind.hpp¶

/*
 * UnionFind.hpp
 *
 *  Created on: 11.08.2014
 *      Author: Marcel Radermacher
 *      Changed a bit by Henning Meyerhenke to reflect union by rank and path compression
 *        as taught in "Algorithms 1"
 */

#ifndef NETWORKIT_STRUCTURES_UNION_FIND_HPP_
#define NETWORKIT_STRUCTURES_UNION_FIND_HPP_

#include <vector>

#include <networkit/Globals.hpp>
#include <networkit/structures/Partition.hpp>

namespace NetworKit {

class UnionFind final {
    std::vector<index> parent;
    std::vector<unsigned char> rank;

public:
    UnionFind(index max_element) : parent(max_element), rank(max_element, 0) { allToSingletons(); }

    void allToSingletons();

    index find(index u);

    void merge(index u, index v);

    Partition toPartition();
};
} /* namespace NetworKit */
#endif // NETWORKIT_STRUCTURES_UNION_FIND_HPP_