1 class Solution
 2 {
 3 public:
 4     const int dx[4] = {1, 0, -1, 0};
 5     const int dy[4] = {0, 1, 0, -1};
 6     void dfs(int x, int y, vector<vector<int>>& grid, vector<vector<int>>& vis)
 7     {
 8         int n = grid.size(), m = grid[0].size();
 9         vis[x][y] = 1;
10         for (int i = 0; i < 4; i++)
11         {
12             int nx = x + dx[i];
13             int ny = y + dy[i];
14             if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == 1 && !vis[nx][ny])
15             {
16                 dfs(nx, ny, grid, vis);
17             }
18         }
19     }
20     int count_connected_components(vector<vector<int>>& grid)
21     {
22         int n = grid.size(), m = grid[0].size();
23         vector<vector<int>> vis(n, vector<int>(m, 0));
24         int cnt = 0;
25         for (int i = 0; i < n; i++)
26         {
27             for (int j = 0; j < m; j++)
28             {
29                 if (!vis[i][j] && grid[i][j] == 1)
30                 {
31                     cnt++;
32                     dfs(i, j, grid, vis);
33                 }
34             }
35         }
36         return cnt;
37     }
38     bool check(vector<vector<int>>& grid)
39     {
40         int cccnt = count_connected_components(grid);
41         return cccnt >= 2 or cccnt == 0; 
42     }
43     int minDays(vector<vector<int>>& grid)
44     {
45         if (check(grid)) return 0;
46         int n = grid.size(), m = grid[0].size();
47         for (int i = 0; i < n; i++)
48         {
49             for (int j = 0; j < m; j++)
50             {
51                 if (grid[i][j] == 1)
52                 {
53                     grid[i][j] = 0;
54                     if (check(grid)) return 1;
55                     grid[i][j] = 1;
56                 }
57             }
58         }
59         return 2;
60     }
61 };

  1 class TarjanSCC
  2 {
  3 private:
  4     const vector<vector<int>>& edges;
  5     vector<int> low, dfn, fa;
  6     int timestamp = -1;
  7     int n;
  8     
  9 private:
 10     // Tarjan 算法求解割点模板
 11     void getCuttingVertex(int u, int parent, vector<int>& ans)
 12     {
 13         low[u] = dfn[u] = ++timestamp;
 14         fa[u] = parent;
 15         int child = 0;
 16         bool iscv = false;
 17         for (int v: edges[u])
 18         {
 19             if (dfn[v] == -1)
 20             {
 21                 ++child;
 22                 getCuttingVertex(v, u, ans);
 23                 low[u] = min(low[u], low[v]);
 24                 if (!iscv && parent != -1 && low[v] >= dfn[u])
 25                 {
 26                     ans.push_back(u);
 27                     iscv = true;
 28                 }
 29             }
 30             else if (v != fa[u]) low[u] = min(low[u], dfn[v]);
 31         }
 32         if (!iscv && parent == -1 && child >= 2) ans.push_back(u);
 33     }
 34 
 35 public:
 36     TarjanSCC(const vector<vector<int>>& _edges): edges(_edges), n(_edges.size()) {}
 37 
 38     int check()
 39     {
 40         low.assign(n, -1);
 41         dfn.assign(n, -1);
 42         fa.assign(n, -1);
 43         timestamp = -1;
 44         
 45         // cutting vertices 存储割点
 46         vector<int> cvs;
 47         // connected components count 存储连通分量个数
 48         int cccnt = 0;
 49         for (int i = 0; i < n; ++i)
 50         {
 51             if (dfn[i] == -1)
 52             {
 53                 ++cccnt;
 54                 getCuttingVertex(i, -1, cvs);
 55             }
 56         }
 57         // 如果连通分量个数大于 1，答案为 0
 58         if (cccnt > 1) return 0;
 59         // 如果存在割点，答案为 1
 60         if (!cvs.empty()) return 1;
 61         return 2;
 62     }
 63 };
 64 
 65 class Solution
 66 {
 67 private:
 68     static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
 69 
 70 public:
 71     int minDays(vector<vector<int>>& grid)
 72     {
 73         int m = grid.size();
 74         int n = grid[0].size();
 75         
 76         // 节点重标号
 77         int landCount = 0;
 78         unordered_map<int, int> relabel;
 79         for (int i = 0; i < m; ++i)
 80         {
 81             for (int j = 0; j < n; ++j)
 82             {
 83                 if (grid[i][j] == 1)
 84                 {
 85                     relabel[i * n + j] = landCount;
 86                     ++landCount;
 87                 }
 88             }
 89         }
 90         if (landCount <= 1) return landCount;
 91 
 92         // 添加图中的边
 93         vector<vector<int>> edges(landCount);
 94         for (int i = 0; i < m; ++i)
 95         {
 96             for (int j = 0; j < n; ++j)
 97             {
 98                 if (grid[i][j] == 1)
 99                 {
100                     for (int d = 0; d < 4; ++d)
101                     {
102                         int ni = i + dirs[d][0];
103                         int nj = j + dirs[d][1];
104                         if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] == 1)
105                         {
106                             edges[relabel[i * n + j]].push_back(relabel[ni * n + nj]);
107                         }
108                     }
109                 }
110             }
111         }
112 
113         auto scc = TarjanSCC(edges);
114         return scc.check();
115     }
116 };