# Simple disjoint-set based implementation

The above forest methodology is actually a disjoint-set data structure, which involves three main operations:

subalgo makeSet(v: a node): v.parent = v <- make a new tree rooted at v subalgo findSet(v: a node): if v.parent == v: return v return findSet(v.parent) subalgo unionSet(v, u: nodes): vRoot = findSet(v) uRoot = findSet(u) uRoot.parent = vRoot algorithm kruskalMST''(G: a graph): sort G's edges by their value for each node n in G: makeSet(n) for each edge e in G: if findSet(e.first) != findSet(e.second): unionSet(e.first, e.second)

This naive implementation leads to `O(n log n)`

time for managing the disjoint-set data structure, leading to `O(m*n log n)`

time for the entire Kruskalâ€™s algorithm.

Found a mistake? Have a question or improvement idea?
Let me know.

Table Of Contents