547. Number of Provinces - Solution & Explanation

Prerequisites

Before attempting this problem, you should be comfortable with:

Graph Representation (Adjacency Matrix) - Understanding how to represent connections between nodes in a 2D matrix
Depth First Search (DFS) - Recursive traversal technique used to explore all reachable nodes from a starting point
Breadth First Search (BFS) - Level-by-level traversal using a queue to explore connected nodes
Union-Find (Disjoint Set Union) - Data structure for efficiently tracking and merging connected components

1. Depth First Search

Intuition

A province is a group of directly or indirectly connected cities. This is essentially finding the number of connected components in an undirected graph. We can use DFS to explore all cities reachable from a starting city, marking them as visited. Each time we start a new DFS from an unvisited city, we have found a new province.

Algorithm

Create a visited array of size n initialized to false.
Initialize province count res to 0.
For each city i from 0 to n-1:
- If city i is not visited:
  - Increment res (found a new province).
  - Run dfs from city i to mark all connected cities as visited.
In the dfs:
- Mark the current node as visited.
- For each neighbor nei that is connected and not visited, recursively call dfs.
Return res.

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        res = 0
        visited = [False] * n

        def dfs(node):
            visited[node] = True
            for nei in range(n):
                if isConnected[node][nei] and not visited[nei]:
                    dfs(nei)

        for i in range(n):
            if not visited[i]:
                dfs(i)
                res += 1

        return res

public class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        boolean[] visited = new boolean[n];
        int res = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i, isConnected, visited, n);
                res++;
            }
        }
        return res;
    }

    private void dfs(int node, int[][] isConnected, boolean[] visited, int n) {
        visited[node] = true;
        for (int nei = 0; nei < n; nei++) {
            if (isConnected[node][nei] == 1 && !visited[nei]) {
                dfs(nei, isConnected, visited, n);
            }
        }
    }
}

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        vector<bool> visited(n, false);
        int res = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i, isConnected, visited, n);
                res++;
            }
        }
        return res;
    }

    void dfs(int node, vector<vector<int>>& isConnected, vector<bool>& visited, int n) {
        visited[node] = true;
        for (int nei = 0; nei < n; nei++) {
            if (isConnected[node][nei] == 1 && !visited[nei]) {
                dfs(nei, isConnected, visited, n);
            }
        }
    }
};

class Solution {
    /**
     * @param {number[][]} isConnected
     * @return {number}
     */
    findCircleNum(isConnected) {
        const n = isConnected.length;
        const visited = new Array(n).fill(false);
        let res = 0;

        const dfs = (node) => {
            visited[node] = true;
            for (let nei = 0; nei < n; nei++) {
                if (isConnected[node][nei] === 1 && !visited[nei]) {
                    dfs(nei);
                }
            }
        };

        for (let i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i);
                res++;
            }
        }

        return res;
    }
}

public class Solution {
    public int FindCircleNum(int[][] isConnected) {
        int n = isConnected.Length;
        bool[] visited = new bool[n];
        int res = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                Dfs(i, isConnected, visited, n);
                res++;
            }
        }
        return res;
    }

    private void Dfs(int node, int[][] isConnected, bool[] visited, int n) {
        visited[node] = true;
        for (int nei = 0; nei < n; nei++) {
            if (isConnected[node][nei] == 1 && !visited[nei]) {
                Dfs(nei, isConnected, visited, n);
            }
        }
    }
}

func findCircleNum(isConnected [][]int) int {
    n := len(isConnected)
    visited := make([]bool, n)
    res := 0

    var dfs func(node int)
    dfs = func(node int) {
        visited[node] = true
        for nei := 0; nei < n; nei++ {
            if isConnected[node][nei] == 1 && !visited[nei] {
                dfs(nei)
            }
        }
    }

    for i := 0; i < n; i++ {
        if !visited[i] {
            dfs(i)
            res++
        }
    }
    return res
}

class Solution {
    fun findCircleNum(isConnected: Array<IntArray>): Int {
        val n = isConnected.size
        val visited = BooleanArray(n)
        var res = 0

        fun dfs(node: Int) {
            visited[node] = true
            for (nei in 0 until n) {
                if (isConnected[node][nei] == 1 && !visited[nei]) {
                    dfs(nei)
                }
            }
        }

        for (i in 0 until n) {
            if (!visited[i]) {
                dfs(i)
                res++
            }
        }
        return res
    }
}

class Solution {
    func findCircleNum(_ isConnected: [[Int]]) -> Int {
        let n = isConnected.count
        var visited = [Bool](repeating: false, count: n)
        var res = 0

        func dfs(_ node: Int) {
            visited[node] = true
            for nei in 0..<n {
                if isConnected[node][nei] == 1 && !visited[nei] {
                    dfs(nei)
                }
            }
        }

        for i in 0..<n {
            if !visited[i] {
                dfs(i)
                res += 1
            }
        }
        return res
    }
}

impl Solution {
    pub fn find_circle_num(is_connected: Vec<Vec<i32>>) -> i32 {
        let n = is_connected.len();
        let mut visited = vec![false; n];
        let mut res = 0;

        fn dfs(node: usize, is_connected: &Vec<Vec<i32>>, visited: &mut Vec<bool>, n: usize) {
            visited[node] = true;
            for nei in 0..n {
                if is_connected[node][nei] == 1 && !visited[nei] {
                    dfs(nei, is_connected, visited, n);
                }
            }
        }

        for i in 0..n {
            if !visited[i] {
                dfs(i, &is_connected, &mut visited, n);
                res += 1;
            }
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

2. Depth First Search (Modifying Input)

Intuition

Instead of using a separate visited array, we can use the diagonal of the adjacency matrix itself to track visited status. Since isConnected[i][i] is always 1 (a city is connected to itself), we can set it to 0 when we visit that city. This saves space but modifies the input.

Algorithm

Initialize province count res to 0.
For each city i from 0 to n-1:
- If isConnected[i][i] equals 1 (not yet visited):
  - Increment res.
  - Run dfs from city i.
In the dfs:
- Set isConnected[node][node] = 0 to mark as visited.
- For each neighbor nei that is connected and whose diagonal is still 1, recursively call dfs.
Return res.

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        res = 0

        def dfs(node):
            isConnected[node][node] = 0
            for nei in range(n):
                if node != nei and isConnected[node][nei] and isConnected[nei][nei]:
                    dfs(nei)

        for i in range(n):
            if isConnected[i][i]:
                dfs(i)
                res += 1

        return res

public class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        int res = 0;

        for (int i = 0; i < n; i++) {
            if (isConnected[i][i] == 1) {
                dfs(i, isConnected, n);
                res++;
            }
        }
        return res;
    }

    private void dfs(int node, int[][] isConnected, int n) {
        isConnected[node][node] = 0;
        for (int nei = 0; nei < n; nei++) {
            if (node != nei && isConnected[node][nei] == 1 && isConnected[nei][nei] == 1) {
                dfs(nei, isConnected, n);
            }
        }
    }
}

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        int res = 0;

        for (int i = 0; i < n; i++) {
            if (isConnected[i][i] == 1) {
                dfs(i, isConnected, n);
                res++;
            }
        }
        return res;
    }

    void dfs(int node, vector<vector<int>>& isConnected, int n) {
        isConnected[node][node] = 0;
        for (int nei = 0; nei < n; nei++) {
            if (node != nei && isConnected[node][nei] == 1 && isConnected[nei][nei] == 1) {
                dfs(nei, isConnected, n);
            }
        }
    }
};

class Solution {
    /**
     * @param {number[][]} isConnected
     * @return {number}
     */
    findCircleNum(isConnected) {
        const n = isConnected.length;
        let res = 0;

        const dfs = (node) => {
            isConnected[node][node] = 0;
            for (let nei = 0; nei < n; nei++) {
                if (
                    node !== nei &&
                    isConnected[node][nei] === 1 &&
                    isConnected[nei][nei] === 1
                ) {
                    dfs(nei);
                }
            }
        };

        for (let i = 0; i < n; i++) {
            if (isConnected[i][i] === 1) {
                dfs(i);
                res++;
            }
        }

        return res;
    }
}

public class Solution {
    public int FindCircleNum(int[][] isConnected) {
        int n = isConnected.Length;
        int res = 0;

        for (int i = 0; i < n; i++) {
            if (isConnected[i][i] == 1) {
                Dfs(i, isConnected, n);
                res++;
            }
        }

        return res;
    }

    private void Dfs(int node, int[][] isConnected, int n) {
        isConnected[node][node] = 0;
        for (int nei = 0; nei < n; nei++) {
            if (node != nei && isConnected[node][nei] == 1 && isConnected[nei][nei] == 1) {
                Dfs(nei, isConnected, n);
            }
        }
    }
}

func findCircleNum(isConnected [][]int) int {
    n := len(isConnected)
    res := 0

    var dfs func(node int)
    dfs = func(node int) {
        isConnected[node][node] = 0
        for nei := 0; nei < n; nei++ {
            if node != nei && isConnected[node][nei] == 1 && isConnected[nei][nei] == 1 {
                dfs(nei)
            }
        }
    }

    for i := 0; i < n; i++ {
        if isConnected[i][i] == 1 {
            dfs(i)
            res++
        }
    }
    return res
}

class Solution {
    fun findCircleNum(isConnected: Array<IntArray>): Int {
        val n = isConnected.size
        var res = 0

        fun dfs(node: Int) {
            isConnected[node][node] = 0
            for (nei in 0 until n) {
                if (node != nei && isConnected[node][nei] == 1 && isConnected[nei][nei] == 1) {
                    dfs(nei)
                }
            }
        }

        for (i in 0 until n) {
            if (isConnected[i][i] == 1) {
                dfs(i)
                res++
            }
        }
        return res
    }
}

class Solution {
    func findCircleNum(_ isConnected: [[Int]]) -> Int {
        var isConnected = isConnected
        let n = isConnected.count
        var res = 0

        func dfs(_ node: Int) {
            isConnected[node][node] = 0
            for nei in 0..<n {
                if node != nei && isConnected[node][nei] == 1 && isConnected[nei][nei] == 1 {
                    dfs(nei)
                }
            }
        }

        for i in 0..<n {
            if isConnected[i][i] == 1 {
                dfs(i)
                res += 1
            }
        }
        return res
    }
}

impl Solution {
    pub fn find_circle_num(mut is_connected: Vec<Vec<i32>>) -> i32 {
        let n = is_connected.len();
        let mut res = 0;

        fn dfs(node: usize, is_connected: &mut Vec<Vec<i32>>, n: usize) {
            is_connected[node][node] = 0;
            for nei in 0..n {
                if node != nei && is_connected[node][nei] == 1 && is_connected[nei][nei] == 1 {
                    dfs(nei, is_connected, n);
                }
            }
        }

        for i in 0..n {
            if is_connected[i][i] == 1 {
                dfs(i, &mut is_connected, n);
                res += 1;
            }
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$ for recursion stack.

3. Breadth First Search

Intuition

BFS provides an alternative to DFS for exploring connected components. Instead of going deep first, we explore all neighbors at the current level before moving to the next. The logic remains the same: start from an unvisited city, explore all reachable cities using a queue, and count each new starting point as a separate province.

Algorithm

Create a visited array of size n initialized to false.
Initialize province count res to 0 and create an empty queue.
For each city i from 0 to n-1:
- If city i is not visited:
  - Increment res.
  - Mark city i as visited and add it to the queue.
  - While the queue is not empty:
    - Dequeue a city node.
    - For each neighbor nei that is connected and not visited, mark it visited and enqueue it.
Return res.

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        visited = [False] * n
        res = 0
        q = deque()

        for i in range(n):
            if not visited[i]:
                res += 1
                visited[i] = True
                q.append(i)
                while q:
                    node = q.popleft()
                    for nei in range(n):
                        if isConnected[node][nei] and not visited[nei]:
                            visited[nei] = True
                            q.append(nei)

        return res

public class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        boolean[] visited = new boolean[n];
        Queue<Integer> q = new LinkedList<>();
        int res = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                res++;
                visited[i] = true;
                q.add(i);
                while (!q.isEmpty()) {
                    int node = q.poll();
                    for (int nei = 0; nei < n; nei++) {
                        if (isConnected[node][nei] == 1 && !visited[nei]) {
                            visited[nei] = true;
                            q.add(nei);
                        }
                    }
                }
            }
        }
        return res;
    }
}

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        vector<bool> visited(n, false);
        queue<int> q;
        int res = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                res++;
                visited[i] = true;
                q.push(i);
                while (!q.empty()) {
                    int node = q.front(); q.pop();
                    for (int nei = 0; nei < n; nei++) {
                        if (isConnected[node][nei] && !visited[nei]) {
                            visited[nei] = true;
                            q.push(nei);
                        }
                    }
                }
            }
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number[][]} isConnected
     * @return {number}
     */
    findCircleNum(isConnected) {
        const n = isConnected.length;
        const visited = new Array(n).fill(false);
        const q = new Queue();
        let res = 0;

        for (let i = 0; i < n; i++) {
            if (!visited[i]) {
                res++;
                visited[i] = true;
                q.enqueue(i);
                while (!q.isEmpty()) {
                    const node = q.dequeue();
                    for (let nei = 0; nei < n; nei++) {
                        if (isConnected[node][nei] && !visited[nei]) {
                            visited[nei] = true;
                            q.enqueue(nei);
                        }
                    }
                }
            }
        }
        return res;
    }
}

public class Solution {
    public int FindCircleNum(int[][] isConnected) {
        int n = isConnected.Length;
        bool[] visited = new bool[n];
        Queue<int> q = new Queue<int>();
        int res = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                res++;
                visited[i] = true;
                q.Enqueue(i);
                while (q.Count > 0) {
                    int node = q.Dequeue();
                    for (int nei = 0; nei < n; nei++) {
                        if (isConnected[node][nei] == 1 && !visited[nei]) {
                            visited[nei] = true;
                            q.Enqueue(nei);
                        }
                    }
                }
            }
        }
        return res;
    }
}

func findCircleNum(isConnected [][]int) int {
    n := len(isConnected)
    visited := make([]bool, n)
    res := 0

    for i := 0; i < n; i++ {
        if !visited[i] {
            res++
            visited[i] = true
            q := []int{i}
            for len(q) > 0 {
                node := q[0]
                q = q[1:]
                for nei := 0; nei < n; nei++ {
                    if isConnected[node][nei] == 1 && !visited[nei] {
                        visited[nei] = true
                        q = append(q, nei)
                    }
                }
            }
        }
    }
    return res
}

class Solution {
    fun findCircleNum(isConnected: Array<IntArray>): Int {
        val n = isConnected.size
        val visited = BooleanArray(n)
        var res = 0

        for (i in 0 until n) {
            if (!visited[i]) {
                res++
                visited[i] = true
                val q = ArrayDeque<Int>()
                q.add(i)
                while (q.isNotEmpty()) {
                    val node = q.removeFirst()
                    for (nei in 0 until n) {
                        if (isConnected[node][nei] == 1 && !visited[nei]) {
                            visited[nei] = true
                            q.add(nei)
                        }
                    }
                }
            }
        }
        return res
    }
}

class Solution {
    func findCircleNum(_ isConnected: [[Int]]) -> Int {
        let n = isConnected.count
        var visited = [Bool](repeating: false, count: n)
        var res = 0

        for i in 0..<n {
            if !visited[i] {
                res += 1
                visited[i] = true
                var q = [i]
                while !q.isEmpty {
                    let node = q.removeFirst()
                    for nei in 0..<n {
                        if isConnected[node][nei] == 1 && !visited[nei] {
                            visited[nei] = true
                            q.append(nei)
                        }
                    }
                }
            }
        }
        return res
    }
}

impl Solution {
    pub fn find_circle_num(is_connected: Vec<Vec<i32>>) -> i32 {
        let n = is_connected.len();
        let mut visited = vec![false; n];
        let mut res = 0;

        for i in 0..n {
            if !visited[i] {
                res += 1;
                visited[i] = true;
                let mut q = VecDeque::new();
                q.push_back(i);
                while let Some(node) = q.pop_front() {
                    for nei in 0..n {
                        if is_connected[node][nei] == 1 && !visited[nei] {
                            visited[nei] = true;
                            q.push_back(nei);
                        }
                    }
                }
            }
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

4. Disjoint Set Union

Intuition

The Union-Find (Disjoint Set Union) data structure is designed for efficiently managing connected components. We start with each city as its own component. As we process connections, we union the components of connected cities. The final number of distinct components equals the number of provinces. Path compression and union by size optimizations make this approach nearly O(1) per operation.

Algorithm

Initialize a DSU with n components, where each city is its own parent.
For each pair of cities (i, j) where isConnected[i][j] == 1:
- Call union(i, j) to merge their components.
- The union operation decrements the component count if the cities were in different components.
Return the final component count from the DSU.

class DSU:
    def __init__(self, n):
        self.Parent = list(range(n + 1))
        self.Size = [1] * (n + 1)
        self.components = n

    def find(self, node):
        if self.Parent[node] != node:
            self.Parent[node] = self.find(self.Parent[node])
        return self.Parent[node]

    def union(self, u, v):
        pu = self.find(u)
        pv = self.find(v)
        if pu == pv:
            return False

        self.components -= 1
        if self.Size[pu] >= self.Size[pv]:
            self.Size[pu] += self.Size[pv]
            self.Parent[pv] = pu
        else:
            self.Size[pv] += self.Size[pu]
            self.Parent[pu] = pv
        return True

    def numOfComps(self):
        return self.components

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        dsu = DSU(n)

        for i in range(n):
            for j in range(n):
                if isConnected[i][j]:
                    dsu.union(i, j)

        return dsu.numOfComps()

class DSU {
    int[] Parent, Size;
    int components;

    public DSU(int n) {
        Parent = new int[n];
        Size = new int[n];
        components = n;
        for (int i = 0; i < n; i++) {
            Parent[i] = i;
            Size[i] = 1;
        }
    }

    public int find(int node) {
        if (Parent[node] != node) {
            Parent[node] = find(Parent[node]);
        }
        return Parent[node];
    }

    public boolean union(int u, int v) {
        int pu = find(u), pv = find(v);
        if (pu == pv) return false;

        components--;
        if (Size[pu] >= Size[pv]) {
            Size[pu] += Size[pv];
            Parent[pv] = pu;
        } else {
            Size[pv] += Size[pu];
            Parent[pu] = pv;
        }
        return true;
    }

    public int numOfComps() {
        return components;
    }
}

public class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        DSU dsu = new DSU(n);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    dsu.union(i, j);
                }
            }
        }
        return dsu.numOfComps();
    }
}

class DSU {
public:
    vector<int> Parent, Size;
    int components;

    DSU(int n) {
        Parent.resize(n);
        Size.assign(n, 1);
        components = n;
        for (int i = 0; i < n; ++i) Parent[i] = i;
    }

    int find(int node) {
        if (Parent[node] != node)
            Parent[node] = find(Parent[node]);
        return Parent[node];
    }

    bool unionSet(int u, int v) {
        int pu = find(u), pv = find(v);
        if (pu == pv) return false;

        components--;
        if (Size[pu] >= Size[pv]) {
            Size[pu] += Size[pv];
            Parent[pv] = pu;
        } else {
            Size[pv] += Size[pu];
            Parent[pu] = pv;
        }
        return true;
    }

    int numOfComps() {
        return components;
    }
};

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        DSU dsu(n);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (isConnected[i][j])
                    dsu.unionSet(i, j);
        return dsu.numOfComps();
    }
};

class DSU {
    constructor(n) {
        this.Parent = Array(n + 1)
            .fill(0)
            .map((_, i) => i);
        this.Size = Array(n + 1).fill(1);
        this.components = n;
    }

    /**
     * @param {number} node
     * @return {number}
     */
    find(node) {
        if (this.Parent[node] !== node) {
            this.Parent[node] = this.find(this.Parent[node]);
        }
        return this.Parent[node];
    }

    /**
     * @param {number} u
     * @param {number} v
     * @return {boolean}
     */
    union(u, v) {
        let pu = this.find(u);
        let pv = this.find(v);
        if (pu === pv) return false;

        this.components--;
        if (this.Size[pu] >= this.Size[pv]) {
            this.Size[pu] += this.Size[pv];
            this.Parent[pv] = pu;
        } else {
            this.Size[pv] += this.Size[pu];
            this.Parent[pu] = pv;
        }
        return true;
    }

    /**
     * @param {number} u
     * @param {number} v
     * @return {boolean}
     */
    numOfComps() {
        return this.components;
    }
}

class Solution {
    /**
     * @param {number[][]} isConnected
     * @return {number}
     */
    findCircleNum(isConnected) {
        const n = isConnected.length;
        const dsu = new DSU(n);

        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                if (isConnected[i][j]) {
                    dsu.union(i, j);
                }
            }
        }
        return dsu.numOfComps();
    }
}

public class DSU {
    private int[] Parent, Size;
    private int components;

    public DSU(int n) {
        Parent = new int[n];
        Size = new int[n];
        components = n;
        for (int i = 0; i < n; i++) {
            Parent[i] = i;
            Size[i] = 1;
        }
    }

    public int Find(int node) {
        if (Parent[node] != node)
            Parent[node] = Find(Parent[node]);
        return Parent[node];
    }

    public bool Union(int u, int v) {
        int pu = Find(u), pv = Find(v);
        if (pu == pv) return false;

        components--;
        if (Size[pu] >= Size[pv]) {
            Size[pu] += Size[pv];
            Parent[pv] = pu;
        } else {
            Size[pv] += Size[pu];
            Parent[pu] = pv;
        }
        return true;
    }

    public int NumOfComps() {
        return components;
    }
}

public class Solution {
    public int FindCircleNum(int[][] isConnected) {
        int n = isConnected.Length;
        var dsu = new DSU(n);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (isConnected[i][j] == 1)
                    dsu.Union(i, j);
        return dsu.NumOfComps();
    }
}

type DSU struct {
    Parent     []int
    Size       []int
    components int
}

func NewDSU(n int) *DSU {
    dsu := &DSU{
        Parent:     make([]int, n),
        Size:       make([]int, n),
        components: n,
    }
    for i := 0; i < n; i++ {
        dsu.Parent[i] = i
        dsu.Size[i] = 1
    }
    return dsu
}

func (dsu *DSU) Find(node int) int {
    if dsu.Parent[node] != node {
        dsu.Parent[node] = dsu.Find(dsu.Parent[node])
    }
    return dsu.Parent[node]
}

func (dsu *DSU) Union(u, v int) bool {
    pu, pv := dsu.Find(u), dsu.Find(v)
    if pu == pv {
        return false
    }
    dsu.components--
    if dsu.Size[pu] >= dsu.Size[pv] {
        dsu.Size[pu] += dsu.Size[pv]
        dsu.Parent[pv] = pu
    } else {
        dsu.Size[pv] += dsu.Size[pu]
        dsu.Parent[pu] = pv
    }
    return true
}

func findCircleNum(isConnected [][]int) int {
    n := len(isConnected)
    dsu := NewDSU(n)
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if isConnected[i][j] == 1 {
                dsu.Union(i, j)
            }
        }
    }
    return dsu.components
}

class DSU(n: Int) {
    private val parent = IntArray(n) { it }
    private val size = IntArray(n) { 1 }
    var components = n
        private set

    fun find(node: Int): Int {
        if (parent[node] != node) {
            parent[node] = find(parent[node])
        }
        return parent[node]
    }

    fun union(u: Int, v: Int): Boolean {
        val pu = find(u)
        val pv = find(v)
        if (pu == pv) return false

        components--
        if (size[pu] >= size[pv]) {
            size[pu] += size[pv]
            parent[pv] = pu
        } else {
            size[pv] += size[pu]
            parent[pu] = pv
        }
        return true
    }
}

class Solution {
    fun findCircleNum(isConnected: Array<IntArray>): Int {
        val n = isConnected.size
        val dsu = DSU(n)
        for (i in 0 until n) {
            for (j in 0 until n) {
                if (isConnected[i][j] == 1) {
                    dsu.union(i, j)
                }
            }
        }
        return dsu.components
    }
}

class DSU {
    private var parent: [Int]
    private var size: [Int]
    var components: Int

    init(_ n: Int) {
        parent = Array(0..<n)
        size = [Int](repeating: 1, count: n)
        components = n
    }

    func find(_ node: Int) -> Int {
        if parent[node] != node {
            parent[node] = find(parent[node])
        }
        return parent[node]
    }

    func union(_ u: Int, _ v: Int) -> Bool {
        let pu = find(u)
        let pv = find(v)
        if pu == pv { return false }

        components -= 1
        if size[pu] >= size[pv] {
            size[pu] += size[pv]
            parent[pv] = pu
        } else {
            size[pv] += size[pu]
            parent[pu] = pv
        }
        return true
    }
}

class Solution {
    func findCircleNum(_ isConnected: [[Int]]) -> Int {
        let n = isConnected.count
        let dsu = DSU(n)
        for i in 0..<n {
            for j in 0..<n {
                if isConnected[i][j] == 1 {
                    _ = dsu.union(i, j)
                }
            }
        }
        return dsu.components
    }
}

struct DSU {
    parent: Vec<usize>,
    size: Vec<usize>,
    components: i32,
}

impl DSU {
    fn new(n: usize) -> Self {
        Self {
            parent: (0..n).collect(),
            size: vec![1; n],
            components: n as i32,
        }
    }

    fn find(&mut self, node: usize) -> usize {
        if self.parent[node] != node {
            self.parent[node] = self.find(self.parent[node]);
        }
        self.parent[node]
    }

    fn union(&mut self, u: usize, v: usize) -> bool {
        let pu = self.find(u);
        let pv = self.find(v);
        if pu == pv {
            return false;
        }
        self.components -= 1;
        if self.size[pu] >= self.size[pv] {
            self.size[pu] += self.size[pv];
            self.parent[pv] = pu;
        } else {
            self.size[pv] += self.size[pu];
            self.parent[pu] = pv;
        }
        true
    }
}

impl Solution {
    pub fn find_circle_num(is_connected: Vec<Vec<i32>>) -> i32 {
        let n = is_connected.len();
        let mut dsu = DSU::new(n);
        for i in 0..n {
            for j in 0..n {
                if is_connected[i][j] == 1 {
                    dsu.union(i, j);
                }
            }
        }
        dsu.components
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

Common Pitfalls

Confusing Nodes with Edges

The adjacency matrix isConnected[i][j] represents whether city i and city j are directly connected. A common mistake is treating the matrix indices as edge indices rather than node indices. Remember that n is the number of cities, not the number of connections.

Forgetting to Mark Nodes as Visited

When performing DFS or BFS, failing to mark a node as visited before or immediately after processing it can lead to infinite loops or counting the same province multiple times. Always mark nodes as visited as soon as they are encountered.

Misunderstanding the Diagonal

The diagonal elements isConnected[i][i] are always 1 (a city is connected to itself). When modifying the input to track visited status, be careful to use the diagonal correctly. Do not confuse self-connections with actual inter-city connections.