DFS - explanation & comments
Approach: O(N^2) runtime, O(N) space for recursive stack - 176ms (97.57%), 15.3MB (10.18%)
DFS - easier to implement than Union Find, but slower big-O runtime (
Approach: O(N^2) runtime, O(N) space for recursive stack - 176ms (97.57%), 15.3MB (10.18%)
DFS - easier to implement than Union Find, but slower big-O runtime (Union-Find method is O(NlogN))
Each row i indicates a connection from i to each item j in row i.
If item is 1, then there's a connection b/w i and j.
We can start with first item, and then recursively traverse that item's row, and continue down that path in DFS manner.
So we started off on row 0, but the nodes connected to i=0 will also be traversed down and we may end up clearing multiple rows just for the first iteration, which gives us one province. The nodes that we traverse will be stored in visited set() so we don't traverse them again. We continue to do it for other rows (new i), as long as it's not visited yet, which will help us find more provinces.
```py []
class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        N = len(isConnected)
        visited = set()

        def dfs(cityI):
            # cityIConnections is a row in isConnected, which contains the city i's connections
            cityIConnections = isConnected[cityI]
            visited.add(cityI) # Add cityI to seen, so we won't dfs it again (because we called it just now!)
            # We want to take all 1's in cityIConnections to put together into a province
            for cityJ in range(N):
                # Check cityJ's connections first before finishing cityI's connections
                if (cityJ not in visited) and (cityIConnections[cityJ] == 1) and (cityI != cityJ):
                    dfs(cityJ)
            # We're done searching cityI's direct connections
            return 
        
        numProvinces = 0
        for cityI in range(N):
            # Each entire dfs recursion set is going to be one province
            if cityI not in visited:
                dfs(cityI)
                numProvinces += 1
        return numProvinces
```
``` cpp []
class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int N = isConnected.size();
        unordered_set<int> visited;

        auto dfs = [&](int cityI, auto& dfs) -> void {
            visited.insert(cityI); // Mark cityI as visited
            for (int cityJ = 0; cityJ < N; ++cityJ) {
                // If cityJ is not visited, there's a connection, and it's not itself
                if (visited.find(cityJ) == visited.end() && isConnected[cityI][cityJ] == 1 && cityI != cityJ) {
                    dfs(cityJ, dfs);
                }
            }
        };

        int numProvinces = 0;
        for (int cityI = 0; cityI < N; ++cityI) {
            if (visited.find(cityI) == visited.end()) {
                dfs(cityI, dfs);
                ++numProvinces;
            }
        }
        return numProvinces;
    }
};
```
``` java []
class Solution {
    public int findCircleNum(int[][] isConnected) {
        int N = isConnected.length;
        Set<Integer> visited = new HashSet<>();

        // Depth-first search function
        void dfs(int cityI) {
            visited.add(cityI); // Mark cityI as visited
            for (int cityJ = 0; cityJ < N; cityJ++) {
                // If cityJ is not visited, there's a connection, and it's not itself
                if (!visited.contains(cityJ) && isConnected[cityI][cityJ] == 1 && cityI != cityJ) {
                    dfs(cityJ);
                }
            }
        }

        int numProvinces = 0;
        for (int cityI = 0; cityI < N; cityI++) {
            if (!visited.contains(cityI)) {
                dfs(cityI);
                numProvinces++;
            }
        }
        return numProvinces;
    }
}
```
['Depth-First Search', 'Python', 'C++', 'Java', 'Python3']