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(const vector<vector<int>> &isConnected) {
        int circle_count = 0;
        vector<bool> visit(isConnected.size(), false);
        for (int i = 0; i < isConnected.size(); ++i) {
            if (!visit[i]) {
                ++circle_count;
                visit[i] = true;
                queue<int> to_check({i});
                while (!to_check.empty()) {
                    int ii = to_check.front();
                    to_check.pop();
                    for (int j = 0; j < isConnected[ii].size(); ++j) {
                        if (isConnected[ii][j] == 1 && !visit[j]) {
                            to_check.push(j);
                            visit[j] = true;
                        }
                    }
                }
            }
        }

        return circle_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;
    }
};