LeetCode 547 Number of Provinces - Example and Complexity Analysis

Trace [[1,1,0],[1,1,0],[0,0,1]].

Initialize: 3 cities, each is its own parent. Provinces = 3.

Check isConnected[0][1] = 1. Union(0, 1). Now 0 and 1 share a root. Provinces = 2.

Check isConnected[0][2] = 0. Skip.

Check isConnected[1][2] = 0. Skip.

(We only need to check upper triangle since matrix is symmetric.)

Count distinct roots: find(0) = 0, find(1) = 0, find(2) = 2. Distinct: {0, 2}. Answer: 2.

$O(n^2 \cdot \alpha(n))$ time to process the matrix. $O(n)$ space.