// weighted quick-union with path compression
int numOfUnions; // number of unions
numOfUnions = numOfElements;
parent = new int[numOfElements];
size = new int[numOfElements];
for (int i = 0; i < numOfElements; i++) {
// find the head/representative of x
parent[x] = parent[parent[x]];
void union(int p, int q) {
if (headOfP == headOfQ) {
// connect the small tree to the larger tree
if (size[headOfP] < size[headOfQ]) {
parent[headOfP] = headOfQ; // set headOfP's parent to be headOfQ
size[headOfQ] += size[headOfP];
parent[headOfQ] = headOfP;
size[headOfP] += size[headOfQ];
boolean connected(int p, int q) {
return find(p) == find(q);
public boolean isBipartite(int[][] graph) {
UF unionfind = new UF(n);
// i is what node each adjacent list is for
for (int i = 0; i < n; i++) {
for (int neighbor : graph[i]) {
// i should not be in the union of its neighbors
if (unionfind.connected(i, neighbor)) {
unionfind.union(graph[i][0], neighbor);