Skip to content

Instantly share code, notes, and snippets.

@manzaloros
Created July 16, 2021 22:36
Show Gist options
  • Save manzaloros/88158dd79aca0a9f10b9cc062027b397 to your computer and use it in GitHub Desktop.
Save manzaloros/88158dd79aca0a9f10b9cc062027b397 to your computer and use it in GitHub Desktop.
Union Find Template
const parent = Array(rows * cols).fill(0).map((value, index) => index);
const rank = Array(rows * cols).fill(0);
const find = (i) => {
if (parent[i] !== i) parent[i] = find(parent[i]);
return parent[i];
};
const union = (x, y) => {
const rootx = find(x);
const rooty = find(y);
if (rootx !== rooty) {
if (rank[rootx] > rank[rooty]) {
parent[rooty] = rootx;
} else if (rank[rootx] < rank[rooty]) {
parent[rootx] = rooty;
} else {
// just use this line if not doing rank
parent[rooty] = rootx;
rank[rootx] += 1;
}
// these two were now unioned
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment