# Simple disjoint-set based implementation

suggest changeThe 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