547_Number_of_Provinces.java

classSolution {
publicintfindCircleNum(int[][] isConnected) {
UnionFinduf = newUnionFind(isConnected.length);

for (introw = 0; row < isConnected.length; row++) {
for (intcol = 0; col < isConnected[row].length; col++) {
if (isConnected[row][col] == 1) {
uf.union(row, col);
 }
 }
 }

returnuf.noOfComponents;
 }

privateclassUnionFind {
privateint[] parents, counts;
privateintnoOfComponents;

publicUnionFind(intn) {
noOfComponents = n;
parents = newint[n];
counts = newint[n];

for (inti = 0; i < parents.length; i++) {
parents[i] = i;
counts[i] = 1;
 }
 }

publicintfind(intnode) {
if (parents[node] == node) {
returnnode;
 }

parents[node] = find(parents[parents[node]]);
returnparents[node];
 }

publicvoidunion(inti, intj) {
intp1 = find(i), p2 = find(j);

if (p1 == p2) {
return;
 }

if (counts[p1] > counts[p2]) {
parents[p2] = p1;
counts[p1] += counts[p2];
 } else {
parents[p1] = p2;
counts[p2] += counts[p1];
 }

 --noOfComponents;
 }
 }
}