547. Number of Provinces

2020, Dec 05 2 mins read

1. Description

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.
A province is a group of directly or indirectly connected cities and no other cities outside of the group.
You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.
Return the total number of provinces.

2. Example

Example 1

Example 1
Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2

Example 2

Example 2
Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3

3. Constraints

1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] is 1 or 0.
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]

4. Solutions

Breadth-First Search

n = isConnected.size()
Time complexity: O($n^2$)
Space complexity: O(n)

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

        vector<bool> visited(n, false);
        int province_count = 0;

        for (int i = 0; i < n; ++i) {
            if (visited[i]) {
                continue;
            }

            ++province_count;

            queue<int> to_visit;
            to_visit.push(i);
            visited[i] = true;

            while (!to_visit.empty()) {
                int city = to_visit.front();
                to_visit.pop();

                for (int j = 0; j < n; ++j) {
                    if (isConnected[city][j] == 1 && !visited[j]) {
                        visited[j] = true;
                        to_visit.push(j);
                    }
                }
            }
        }

        return province_count;
    }
};

Union Find

n = isConnected.size()
Time complexity: O($n^2$)
Space complexity: O(n)

class Solution {
public:
    int find(vector<int> &parent, int index) {
        if (parent[index] != index) {
            parent[index] = find(parent, parent[index]);
        }
        return parent[index];
    }

    void unite(vector<int> &parent, int index1, int index2) {
        parent[find(parent, index1)] = find(parent, index2);
    }

    int findCircleNum(vector<vector<int>> &isConnected) {
        int city_count = isConnected.size();
        vector<int> parent(city_count);
        for (int i = 0; i < city_count; i++) {
            parent[i] = i;
        }

        for (int i = 0; i < city_count; i++) {
            for (int j = i + 1; j < city_count; j++) {
                if (isConnected[i][j] == 1) {
                    unite(parent, i, j);
                }
            }
        }

        int circle_count = 0;
        for (int i = 0; i < city_count; i++) {
            if (parent[i] == i) {
                ++circle_count;
            }
        }
        return circle_count;
    }
};