Leetcode 547. Number of Provinces

medium

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.

Depth First Search

When the question is similar to the island count problem, you can solve it by dfs with return 0 or return 1.

class Solution {
    vector<bool> visited;
    int dfs(int v, vector<vector<int>>& adj) {
        if (visited[v])
            return 0;
        
        visited[v] = true;
        for (int i=0; i<adj[v].size(); i++) {
            if (i == v) 
                continue;
            if (adj[v][i])
                dfs(i, adj);
        }
        return 1;
    }
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        visited.resize(isConnected.size(), false);
        
        int province = 0;
        for (int i=0; i<isConnected.size(); i++) {
            province += dfs(i, isConnected);
        }
        return province;
    }
};