content: package codingquestions.leetcode;
  
  /**
   * 547. Number of Provinces
   * Solved
   * Medium
   * Topics
   * Companies
   * 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.
   * <p>
   * A province is a group of directly or indirectly connected cities and no other cities outside of the group.
   * <p>
   * 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.
   * <p>
   * Return the total number of provinces.
   **/
  public class NumberofProvinces {
      public int findCircleNum(int[][] isConnected) {
          int n = isConnected.length;
          boolean[] visited = new boolean[n];
          int cnt = 0;
          for (int i = 0; i < n; i++) {
              if (!visited[i]) {
                  visited[i] = true;
                  dfs(isConnected, i, visited);
                  cnt++;
              }
          }
          return cnt;
      }
  
      private void dfs(int[][] isConnected, int i, boolean[] visited) {
          for (int j = 0; j < isConnected.length; j++) {
              if (!visited[j] && isConnected[i][j] == 1) {
                  visited[j] = true;
                  dfs(isConnected, j, visited);
              }
          }
      }
  }
  