This is one of those problems where the clean idea matters more than the amount of code. For 1568. Minimum Number of Days to Disconnect Island, the solution in this repository is mainly a graph traversal solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: graph traversal.
The notes already sitting in the source point us in the right direction:
- https://leetcode.com/problems/minimum-number-of-days-to-disconnect-island/discuss/819303/Python-you-need-at-most-2-days
- time: O(m^2*n^2)
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are getConns, minDays, APUtil, AP, visited.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- The queue gives the solution a level-by-level or frontier-style traversal.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(m^2*n^2)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//https://leetcode.com/problems/minimum-number-of-days-to-disconnect-island/discuss/819303/Python-you-need-at-most-2-days
02//Runtime: 476 ms, faster than 18.56% of C++ online submissions for Minimum Number of Days to Disconnect Island.
03//Memory Usage: 31.9 MB, less than 16.52% of C++ online submissions for Minimum Number of Days to Disconnect Island.
04//time: O(m^2*n^2)
05class Solution {
06public:
07 int m, n;
08 vector<vector<int>> dirs;
09 vector<vector<bool>> visited;
10
11 int getConns(vector<vector<int>>& grid){
12 int conns = 0;
13 visited = vector<vector<bool>>(m, vector<bool>(n, false));
14
15 for(int i = 0; i < m; ++i){
16 for(int j = 0; j < n; ++j){
17 if(!grid[i][j] || visited[i][j]) continue;
18
19 ++conns;
20 queue<pair<int, int>> q;
21 q.push({i, j});
22 visited[i][j] = true;
23
24 while(!q.empty()){
25 pair<int, int> p = q.front(); q.pop();
26
27 for(vector<int>& dir : dirs){
28 int ni = p.first + dir[0];
29 int nj = p.second + dir[1];
30 if(ni < 0 || ni >= m || nj < 0 || nj >= n ||
31 !grid[ni][nj] || visited[ni][nj])
32 continue;
33 visited[ni][nj] = true;
34 q.push({ni,nj});
35 }
36 }
37 }
38 }
39
40 return conns;
41 }
42
43 int minDays(vector<vector<int>>& grid) {
44 m = grid.size();
45 n = grid[0].size();
46
47 dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}};
48
49 int conns = getConns(grid);
50 // cout << "conns: " << conns << endl;
51 if(conns == 0 || conns >= 2) return 0;
52
53 for(int i = 0; i < m; ++i){
54 for(int j = 0; j < n; ++j){
55 if(!grid[i][j]) continue;
56 grid[i][j] = 0;
57 conns = getConns(grid);
58 // cout << "conns: " << conns << endl;
59 /*
60 [[0,0,0],[0,1,0],[0,0,0]]
61 is also needed to be disconnected,
62 i.e. to destroy the island
63 */
64 if(conns == 0 || conns >= 2)
65 return 1;
66 grid[i][j] = 1;
67 }
68 }
69
70 return 2;
71 }
72};
73
74//Tarjan’s algorithm for finding articulation points
75//https://leetcode.com/problems/minimum-number-of-days-to-disconnect-island/discuss/819643/Java-Tarjan-4ms-with-explain
76//https://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/
77//Runtime: 24 ms, faster than 97.01% of C++ online submissions for Minimum Number of Days to Disconnect Island.
78//Memory Usage: 11.5 MB, less than 72.15% of C++ online submissions for Minimum Number of Days to Disconnect Island.
79class Solution {
80public:
81 int m, n;
82 vector<vector<int>> dirs;
83 vector<vector<int>> graph;
84
85 int getConns(vector<vector<int>>& grid){
86 int conns = 0;
87 vector<vector<bool>> visited(m, vector<bool>(n, false));
88
89 for(int i = 0; i < m; ++i){
90 for(int j = 0; j < n; ++j){
91 if(!grid[i][j] || visited[i][j]) continue;
92
93 ++conns;
94 queue<pair<int, int>> q;
95 q.push({i, j});
96 visited[i][j] = true;
97
98 while(!q.empty()){
99 pair<int, int> p = q.front(); q.pop();
100
101 for(vector<int>& dir : dirs){
102 int ni = p.first + dir[0];
103 int nj = p.second + dir[1];
104 if(ni < 0 || ni >= m || nj < 0 || nj >= n ||
105 !grid[ni][nj] || visited[ni][nj])
106 continue;
107 visited[ni][nj] = true;
108 q.push({ni,nj});
109 }
110 }
111 }
112 }
113
114 return conns;
115 }
116
117 bool APUtil(int u, int& time, vector<bool>& visited, vector<int>& disc,
118 vector<int>& low, vector<int>& parent){
119 int child_count = 0;
120 visited[u] = true;
121 ++time;
122 disc[u] = low[u] = time;
123 // cout << "visit: " << u/n << ", " << u%n << " at " << time << endl;
124 for(int& v : graph[u]){
125 if(!visited[v]){
126 ++child_count;
127 parent[v] = u;
128 bool res = APUtil(v, time, visited, disc, low, parent);
129 if(res) return true;
130 /*
131 if the subtree rooted at v has
132 a back edge connected to somewhere higher than u,
133 then low[u] will be updated
134 */
135 low[u] = min(low[u], low[v]);
136
137 if(parent[u] == -1 && child_count > 1)
138 return true;
139
140 /*
141 u: not root nor leaf,
142 and one of its children's subtree doesn't have backedge
143 */
144 if(parent[u] != -1 && low[v] >= disc[u])
145 return true;
146 }else if(v != parent[u]){
147 //?
148 low[u] = min(low[u], disc[v]);
149 }
150 }
151
152 return false;
153 }
154
155 bool AP(){
156 vector<bool> visited(m*n, false);
157 vector<int> disc(m*n, 0);
158 vector<int> low(m*n, 0);
159 vector<int> parent(m*n, -1);
160
161 int time = 0;
162 for(int i = 0; i < m*n; ++i){
163 if(graph[i].empty() || visited[i]) continue;
164 // cout << "root: " << i/n << ", " << i%n << " has " << graph[i].size() << " children" << endl;
165 bool res = APUtil(i, time, visited, disc, low, parent);
166 if(res) return true;
167 }
168
169 for(int i = 0; i < m*n; ++i){
170 if(graph[i].empty()) continue;
171 // cout << i/n << ", " << i%n << " , disc: " << disc[i] << ", low: " << low[i] << ", parent: " << parent[i]/n << ", " << parent[i]%n << endl;
172 }
173
174 return false;
175 };
176
177 int getid(int i, int j){
178 //*n, not *m !!
179 return i*n + j;
180 };
181
182 int minDays(vector<vector<int>>& grid) {
183 m = grid.size();
184 n = grid[0].size();
185
186 dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}};
187
188 int conns = getConns(grid);
189 // cout << "conns: " << conns << endl;
190 if(conns == 0 || conns >= 2) return 0;
191
192 int sum = 0;
193
194 for(int i = 0; i < m; ++i){
195 for(int j = 0; j < n; ++j){
196 sum += grid[i][j];
197 }
198 }
199
200 if(sum <= 2) return sum;
201
202 graph = vector<vector<int>>(m*n);
203 // cout << "m: " << m << ", n: " << n << endl;
204
205 for(int i = 0; i < m; ++i){
206 for(int j = 0; j < n; ++j){
207 if(!grid[i][j]) continue;
208 int cid = getid(i, j);
209 // cout << "(" << i << ", " << j << "): ";
210 for(vector<int>& dir : dirs){
211 int ni = i + dir[0];
212 int nj = j + dir[1];
213 if(ni < 0 || ni >= m || nj < 0 || nj >= n || !grid[ni][nj])
214 continue;
215 int nid = getid(ni, nj);
216 graph[cid].push_back(nid);
217 // cout << "(" << ni << ", " << nj << "), ";
218 // graph[nid].push_back(cid); //duplicate
219 }
220 // cout << endl;
221 }
222 }
223
224 //can find articulation point, so only need one cut
225 if(AP()) return 1;
226 return 2;
227 }
228};Cost
Complexity
Time
O(m^2*n^2)
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.