• Time:O(n^2)
• Space:O(n)

C++

``````class UF {
public:
UF(int n) : count(n), id(n) {
iota(begin(id), end(id), 0);
}

void union_(int u, int v) {
const int i = find(u);
const int j = find(v);
if (i == j)
return;
id[i] = j;
--count;
}

int getCount() const {
return count;
}

private:
int count;
vector<int> id;

int find(int u) {
return id[u] == u ? u : id[u] = find(id[u]);
}
};

class Solution {
public:
int findCircleNum(vector<vector<int>>& M) {
const int n = M.size();
UF uf(n);

for (int i = 0; i < n; ++i)
for (int j = i; j < n; ++j)
if (M[i][j] == 1)
uf.union_(i, j);

return uf.getCount();
}
};
``````

JAVA

``````class UF {
public UF(int n) {
count = n;
id = new int[n];
for (int i = 0; i < n; ++i)
id[i] = i;
}

public void union(int u, int v) {
final int i = find(u);
final int j = find(v);
if (i == j)
return;
id[i] = j;
--count;
}

public int getCount() {
return count;
}

private int count;
private int[] id;

private int find(int u) {
return id[u] == u ? u : (id[u] = find(id[u]));
}
}

class Solution {
public int findCircleNum(int[][] M) {
final int n = M.length;
UF uf = new UF(n);

for (int i = 0; i < n; ++i)
for (int j = i; j < n; ++j)
if (M[i][j] == 1)
uf.union(i, j);

return uf.getCount();
}
}
``````

Python

``````class UF:
def __init__(self, n: int):
self.count = n
self.id = list(range(n))

def union(self, u: int, v: int) -> None:
i = self.find(u)
j = self.find(v)
if i == j:
return
self.id[i] = j
self.count -= 1

def find(self, u: int) -> int:
if self.id[u] != u:
self.id[u] = self.find(self.id[u])
return self.id[u]

class Solution:
def findCircleNum(self, M: List[List[int]]) -> int:
n = len(M)
uf = UF(n)

for i in range(n):
for j in range(i, n):
if M[i][j] == 1:
uf.union(i, j)

return uf.count
``````