unionFind class method find has extra step. It does compression even if it is not needed.
while (p != root) { int next = id[p]; id[p] = root; p = next; }
can be modified to the following to bypass unnecessary step
while (id[p] != root) { int next = id[p]; id[p] = root; p = next; }