コード
public class ChristmasTreeDecoration {
public int solve(int[] col, int[] x, int[] y) {
int N = col.length;
UnionFind uf = new UnionFind(N);
for (int i = 0; i < y.length; i++) {
if (col[x[i] - 1] != col[y[i] - 1]) {
uf.unite(x[i] - 1, y[i] - 1);
}
}
int groups = 1;
for (int i = 0; i < N; i++) {
if (!uf.isSame(0, i)) {
groups++;
uf.unite(0, i);
}
}
return groups - 1;
}
class UnionFind {
int[] parts;
UnionFind(int n) {
parts = new int[n];
for (int i = 0; i < n; i++)
parts[i] = i;
}
public int find(int x) {
if (parts[x] == x)
return x;
return parts[x] = find(parts[x]);
}
public Boolean isSame(int x, int y) {
return find(x) == find(y);
}
public void unite(int x, int y) {
if (find(x) == find(y))
return;
parts[find(x)] = find(y);
}
}
}
