equal
deleted
inserted
replaced
30 * the find operation uses path compression. |
30 * the find operation uses path compression. |
31 * This is a very simple but efficient implementation, providing |
31 * This is a very simple but efficient implementation, providing |
32 * only four methods: join (union), find, insert and size. |
32 * only four methods: join (union), find, insert and size. |
33 * For more features see the \ref UnionFindEnum class. |
33 * For more features see the \ref UnionFindEnum class. |
34 * |
34 * |
|
35 * It is primarily used in Kruskal algorithm for finding minimal |
|
36 * cost spanning tree in a graph. |
|
37 * \sa kruskal() |
|
38 * |
35 * \pre The elements are automatically added only if the map |
39 * \pre The elements are automatically added only if the map |
36 * given to the constructor was filled with -1's. Otherwise you |
40 * given to the constructor was filled with -1's. Otherwise you |
37 * need to add all the elements by the \ref insert() method. |
41 * need to add all the elements by the \ref insert() method. |
|
42 * \bug It is not clear what the constructor parameter is used for. |
38 */ |
43 */ |
39 |
44 |
40 template <typename T, typename TIntMap> |
45 template <typename T, typename TIntMap> |
41 class UnionFind { |
46 class UnionFind { |
42 |
47 |