Session 50: Graph Implementation Lab

Original Session

Date: 15 March 2025

Topic: Graph IL

Concept: BFS
Create Quque.
Add first element in Queue.
Traverse Queue and put children of every polled element to Queue.

Programs

1. 547. Number of Provinces
   1. leetcode here

      private void dfs(int[][] isConnected, boolean[] vis, int i) {
              if (vis[i]) return;
              vis[i] = true;
      
              int n = isConnected.length;
              for (int j = 0; j < n; j++) {
                  if (isConnected[i][j] == 1) {
                      dfs(isConnected, vis, j);
                  }
              }
          }
      
          public int findCircleNum(int[][] isConnected) {
              int n = isConnected.length;
              boolean[] vis = new boolean[n];
              int ans = 0;
      
              for (int i = 0; i < n; i++) {
                  if (!vis[i]) {
                      ans++;
                      dfs(isConnected, vis, i);
                  }
              }
              return ans;
          }

2. 130. Surrounded Regions
   1. leetcode here

      private void dfs(char[][] board, int i, int j, int m, int n) {
      
              if (i<0 || j<0|| i>=m || j>=n || board[i][j] != 'O') {
                  return;
              }
              board[i][j] = '$';
              dfs(board, i-1, j, m, n);
              dfs(board, i+1, j, m, n);
              dfs(board, i, j-1, m, n);
              dfs(board, i, j+1, m, n);
          }
      
          public void solve(char[][] board) {
              int m = board.length;
              if (m==0) return;
              int n = board[0].length;
      
              for (int i=0; i<m; i++) {
                  if (board[i][0] == 'O') dfs(board, i, 0, m, n); // first col
                  if (board[i][n-1] == 'O') dfs(board, i, n-1, m, n); // second col
              }
      
              for (int j=0; j<n; j++) {
                  if (board[0][j] == 'O') dfs(board, 0, j, m, n); // first row
                  if (board[m-1][j] == 'O') dfs(board, m-1, j, m, n); // last row
              }
      
              for (int i=0; i<m; i++) {
                  for (int j=0; j<n; j++) {
      
                      if (board[i][j] == 'O') board[i][j] = 'X';
                      if (board[i][j] == '$') board[i][j] = 'O';
                  }
              }
          }