LeetCode 547 Number of Provinces - Strategy

$1.$ Initialize DSU with $n$ nodes, count = n.

$2.$ Iterate through the matrix isConnected[i][j].

$3.$ If isConnected[i][j] = 1 and find(i) != find(j), union them and decrement count.

$4.$ Return count.

Each successful union reduces components by one. Final count is the number of provinces. Time: $O(n^2 \cdot \alpha(n))$ due to matrix traversal. Space: $O(n)$ for the DSU arrays. You could also solve this with DFS or BFS, but DSU is cleaner here.