Minimum Number of Days to Disconnect Island LeetCode solution in C++

1
class Solution {
2
 public:
3
  int minDays(vector<vector<int>> &grid) {
4
    // if the graph has already greater than 1 components than ans is 0
5
    // if the graph has any articulation point than ans is 1
6
    // else ans is 2
7
    int n = grid.size();
8
    int m = grid[0].size();
9
    int count = 0;
10
    // discovery time
11
    vector<vector<int>> disc(n, vector<int>(m, 0));
12
    // low time
13
    vector<vector<int>> low(n, vector<int>(m, 0));
14
    // visited array
15
    vector<vector<bool>> visited(n, vector<bool>(m, false));
16
    // direction array
17
    int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
18
    // if ok is true means there is a articulation point in the graph
19
    bool ok = false;
20
    // dfs call
21
    function<void(int, int, int &, int)> dfs = [&](int x, int y, int &time, int p) {
22
      // mark the nodes as visited and update their low and disc time
23
      visited[x][y] = true;
24
      disc[x][y] = low[x][y] = time++;
25
      // for root if there are more than 1 recursive tree than root is a
26
      // articulation point
27
      int rootCall = 0;
28
      // going in all direction and making a dfs call
29
      for (int i = 0; i < 4; i++) {
30
        int newX = x + dir[i][0];
31
        int newY = y + dir[i][1];
32
        // if child cordinates are valid and there is a 1 at that point ans also
33
        // it is not parent
34
        if (newX >= 0 && newX < n && newY >= 0 && newY < m && grid[newX][newY] == 1 &&
35
            newX * m + newY != p) {
36
          if (!visited[newX][newY]) {
37
            dfs(newX, newY, time, x * m + y);
38
            // update the low time
39
            low[x][y] = min(low[x][y], low[newX][newY]);
40
            // checking whether [x,y] is articulation point or not
41
            if (p == -1) {
42
              rootCall++;
43
            } else if (disc[x][y] <= low[newX][newY]) {
44
              ok = true;
45
            }
46
          } else {
47
            // updating the low time
48
            low[x][y] = min(low[x][y], disc[newX][newY]);
49
          }
50
        }
51
      }
52
      // if root and more than 1 recurive tree formed than articulation point
53
      if (p == -1 && rootCall > 1) {
54
        ok = true;
55
      }
56
    };
57
    // counting the number of 1's and making dfs call
58
    int to1 = 0;
59
    for (int i = 0; i < n; i++) {
60
      for (int j = 0; j < m; j++) {
61
        if (grid[i][j] == 1) {
62
          to1++;
63
          if (!visited[i][j]) {
64
            int time = 1;
65
            dfs(i, j, time, -1);
66
            count++;
67
          }
68
        }
69
      }
70
    }
71

72
    if (count > 1) {
73
      // if more than one components are formed
74
      return 0;
75
    } else if (ok) {
76
      // if onlu one component is formed and there is a articulation point
77
      return 1;
78
    } else {
79
      // if total number of 1 is 1
80
      if (to1 == 1) {
81
        return 1;
82
      } else if (to1 == 0) {
83
        // if total number of 1 is 0
84
        return 0;
85
      }
86
      // else
87
      return 2;
88
    }
89
  }
90
};