LC-0547 Medium LeetCode

547. Number of Provinces

Depth-First Search Breadth-First Search Union Find Graph

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 68% Topics: Depth-First Search, Breadth-First Search, Union Find, Graph

View full problem on LeetCode

Also on leetcode.ca (community mirror)

Reading material

Trees & Traversals 18 min Union–Find (DSU) 12 min Graphs 16 min

Reference solution (spoiler · java)

import java.util.*;

class Solution {
    int[] parent;

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        int count = n;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < isConnected[i].length && j < n; j++) {
                if (i != j && isConnected[i][j] == 1) {
                    int a = find(i), b = find(j);
                    if (a != b) { parent[a] = b; count--; }
                }
            }
        }
        return count;
    }
}

Solution from kamyu104/LeetCode-Solutions · MIT