leetcode 1568. 使陆地分离的最少天数并查集+tarjan求割点 好题

使陆地分离的最少天数 给你一个由若干 0 和 1 组成的二维网格 grid ，其中 0 表示水，而 1 表示陆地。岛屿由水平方向或竖直方向上相邻的 1 （陆地）连接形成。

如果 恰好只有一座岛屿 ，则认为陆地是 连通的 ；否则，陆地就是 分离的 。

一天内，可以将任何单个陆地单元（1）更改为水单元（0）。

返回使陆地分离的最少天数。

示例 1：

输入：grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]] 输出：2 解释：至少需要 2 天才能得到分离的陆地。 将陆地 grid[1][1] 和 grid[0][2] 更改为水，得到两个分离的岛屿。

示例 2：

输入：grid = [[1,1]] 输出：2 解释：如果网格中都是水，也认为是分离的 ([[1,1]] -> [[0,0]])，0 岛屿。

示例 3：

输入：grid = [[1,0,1,0]] 输出：0

示例 4：

输入：grid = [[1,1,0,1,1], [1,1,1,1,1], [1,1,0,1,1], [1,1,0,1,1]] 输出：1

示例 5：

输入：grid = [[1,1,0,1,1], [1,1,1,1,1], [1,1,0,1,1], [1,1,1,1,1]] 输出：2

提示：

1 <= grid.length, grid[i].length <= 30 grid[i][j] 为 0 或 1

通过次数1,451 提交次数3,100

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/minimum-number-of-days-to-disconnect-island 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

每个格子看成点，共n*m个点，我们把相邻的1连边，于是得到一张无向图， 很容易发现

只要有割点就能只需要一次操作，

没有割点则需要2次操作，如图

先用并查集判联通块个数，再tarjan求割点即可得到答案

复杂度$O(n\ast m)$

leetcode上永远是java比c++快

并查集模板如下c++

int fa(int x) { return pre[x]==x ? x : (pre[x]=fa(pre[x])); } void union_xy(int x, int y) { x = fa(x), y = fa(y); if(x ^ y) pre[y] = x; }

无向图tarjan求割点模板如下c++

//无向图求割点 void tarjan(int u) { low[u] = dfn[u] = ++timer; int son = 0; for(int i=0; i<(int)G[u].size(); i++) { int v = G[u][i]; if(!dfn[v]) { son ++; tarjan(v); low[u] = min(low[u], low[v]); if(u!=1 && low[v]>=dfn[u]) ans.insert(u); else if(u==1 && son>1) ans.insert(u); } else //这个else不要也能ac poj1144 ??? low[u] = min(low[u], dfn[v]); } }

完整代码c++

// #define debug #ifdef debug #include <time.h> #include "win_majiao.h" #endif #include <iostream> #include <algorithm> #include <vector> #include <string.h> #include <map> #include <set> #include <stack> #include <queue> #include <math.h> #define MAXN (4096<<8) #define ll long long int #define INF (0x7f7f7f7f) #define fori(lef, rig) for(int i=lef; i<=rig; i++) #define forj(lef, rig) for(int j=lef; j<=rig; j++) #define fork(lef, rig) for(int k=lef; k<=rig; k++) #define QAQ (0) using namespace std; #define show(x...) \ do { \ cout << "\033[31;1m " << #x << " -> "; \ err(x); \ } while (0) void err() { cout << "\033[39;0m" << endl; } template<typename T, typename... A> void err(T a, A... x) { cout << a << ' '; err(x...); } namespace FastIO{ char print_f[105]; void read() {} void print() { putchar('\n'); } template <typename T, typename... T2> inline void read(T &x, T2 &... oth) { x = 0; char ch = getchar(); ll f = 1; while (!isdigit(ch)) { if (ch == '-') f *= -1; ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - 48; ch = getchar(); } x *= f; read(oth...); } template <typename T, typename... T2> inline void print(T x, T2... oth) { ll p3=-1; if(x<0) putchar('-'), x=-x; do{ print_f[++p3] = x%10 + 48; } while(x/=10); while(p3>=0) putchar(print_f[p3--]); putchar(' '); print(oth...); } } // namespace FastIO using FastIO::print; using FastIO::read; int n, m, pre[MAXN], dfn[MAXN], low[MAXN], mark[MAXN], timer, NM, ge_cnt, one; int dr[] = { 1, -1, 0, 0 }, dc[] = { 0, 0, 1, -1 }; vector<int> G[MAXN]; #define ID(i,j) (i*n+j) #define cls(x) (memset(x, 0, sizeof(x))) void init(vector<vector<int>>& mtx) { n = mtx.size(), m = mtx[0].size(); NM = n * m; for(int i=0; i<=NM; i++) G[i].clear(); one = ge_cnt = 0; timer = -1; for(int i=0; i<=NM; i++) pre[i] = i, dfn[i] = low[i] = -1, mark[i] = 0; } int fa(int x) { return pre[x]==x ? x : (pre[x]=fa(pre[x])); } void union_xy(int x, int y) { x = fa(x), y = fa(y); if(x ^ y) pre[y] = x; } void tarjan(int u, int ro) { // show(u, timer); low[u] = dfn[u] = ++timer; int son = 0; for(int i=0; i<(int)G[u].size(); i++) { int v = G[u][i]; if(-1 == dfn[v]) { son ++; tarjan(v, ro); low[u] = min(low[u], low[v]); if(u!=ro && low[v]>=dfn[u]) ge_cnt ++; else if(u==ro && son>1) ge_cnt ++; } else low[u] = min(low[u], dfn[v]); } } class Solution { public: int minDays(vector<vector<int>>& mtx) { init(mtx); for(int i=0; i<n; i++) for(int j=0; j<m; j++) { int u = i * m + j; if(!mtx[i][j]) continue ; one ++; mark[u] = true; for(int k=0; k<4; k++) { int nr = i + dr[k], nc = j + dc[k]; if(nr<0 || nc<0 || nr>=n || nc>=m) continue ; if(!mtx[i][j] || !mtx[nr][nc]) continue ; int v = nr * m + nc; mark[u] = mark[v] = true; G[u].push_back(v); union_xy(u, v); } } int cnt = 0; //联通块个数 for(int i=0; i<NM; i++) { if(!mark[i] || fa(i) != i) continue ; cnt ++; } if(cnt > 1) return 0; for(int i=0; i<n; i++) for(int j=0; j<m; j++) { if(-1==dfn[i*m+j] && mark[i*m+j]) tarjan(i*m+j, i*m+j); } // one特判只有一个点 // 因为割点的定义是 删掉后会生成2个或2个以上的联通块 if(one == 1) return 1; //割点个数为 0 说明至少要两次 return ge_cnt == 0 ? 2 : 1; } }; #ifdef debug signed main() { // vector<vector<int> > vec = {{0,1,1,0},{0,1,1,0},{0,0,0,0}}; // vector<vector<int> > vec = { // {1,1,0,1,1}, // {1,1,1,1,1}, // {1,1,0,1,1}, // {1,1,0,1,1} // }; // vector<vector<int> > vec = {{1,0,1,0}}; vector<vector<int> > vec = {{0,0,0},{0,1,0},{0,0,0}}; Solution s; cout << s.minDays(vec) << endl; return 0; } #endif /** [[0,1,1,0],[0,1,1,0],[0,0,0,0]] [[1,1]] [[1,0,1,0]] [[1,1,0,1,1],[1,1,1,1,1],[1,1,0,1,1],[1,1,0,1,1]] [[1,1,0,1,1],[1,1,1,1,1],[1,1,0,1,1],[1,1,1,1,1]] [[0,0,0],[0,1,0],[0,0,0]] */

java代码如下

// import org.omg.PortableInterceptor.INACTIVE; // import sun.nio.cs.ext.MacThai; import java.io.*; import java.math.BigDecimal; import java.math.BigInteger; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.Scanner; class Solution { public static final int MAXN = 1024<<2; public int pre[] = new int[MAXN], low[] = new int[MAXN], dfn[] = new int[MAXN], dr[] = { 1, -1, 0, 0 }, dc[] = { 0, 0, 1, -1 }, n = 0, m = 0, NM = 0, ge_cnt = 0, one = 0, timer = 0; public boolean vis[] = new boolean[MAXN]; int fa(int x) { return pre[x]==x ? x : (pre[x]=fa(pre[x])); } void union_xy(int x, int y) { x = fa(x); y = fa(y); if(x != y) pre[y] = x; } ArrayList<Integer> G[] = new ArrayList[MAXN]; void init(int mtx[][]) { n = mtx.length; m = mtx[0].length; NM = n * m; for(int i=0; i<=NM; i++) { pre[i] = i; low[i] = -1; dfn[i] = -1; if(null == G[i]) G[i] = new ArrayList<>(); G[i].clear(); } timer = -1; ge_cnt = one = 0; } void tarjan(int u, int ro) { dfn[u] = low[u] = ++ timer; int son = 0; for(int v : G[u]) { if(-1 == dfn[v]) { son ++; tarjan(v, u); low[u] = Math.min(low[u], low[v]); if(u != ro && low[v] >= dfn[u]) ge_cnt ++; else if(u == ro && son > 1) ge_cnt ++; } else low[u] = Math.min(low[u], dfn[v]); } } public int minDays(int[][] mtx) { init(mtx); for(int i=0; i<n; i++) for(int j=0; j<m; j++) { if(1 != mtx[i][j]) continue; one ++; int u = i * m + j, v = 0; for(int k=0; k<4; k++) { int nr = i + dr[k], nc = j + dc[k]; if(nr<0 || nc<0 || nr>=n || nc>=m) continue; if(1 != mtx[nr][nc]) continue ; v = nr * m + nc; G[u].add(v); union_xy(u, v); } } if(1 == one) return 1; int rocnt = 0; for(int i=0; i<n; i++) for(int j=0; j<m; j++) { int P = i * m + j; rocnt += (1==mtx[i][j] && pre[P]==P ? 1 : 0); } // System.out.println("rocnt:" + rocnt); if(rocnt > 1) return 0; for(int i=0; i<NM; i++) if(-1==dfn[i]) tarjan(i, i); return ge_cnt == 0 ? 2 : 1; } } public class Main { public static final boolean debug = true; public static String INPATH = "C:\\Users\\majiao\\Desktop\\test.txt", OUTPATH = "C:\\Users\\majiao\\Desktop\\out.txt"; public static StreamTokenizer tok; public static BufferedReader cin; public static PrintWriter cout; public static long start_time = 0, out_time = 0; public static int n, m, K, Q, MAXN = (int)1e5+7, INF = 0x3f3f3f3f; public static byte buf[] = new byte[MAXN]; public static void main(String[] args) throws IOException { main_init(); if(debug) { start_time = System.currentTimeMillis(); } if(false) { System.setOut(new PrintStream(OUTPATH)); } Solution s = new Solution(); int mtx[][] = { {1,1,0,1,1}, {1,1,1,1,1}, {1,1,0,1,1}, {1,1,1,1,1} }; cout.println(s.minDays(mtx)); if(debug) { out_time = System.currentTimeMillis(); cout.printf("run time : %d ms\n", out_time-start_time); } cout.flush(); } public static void main_init() { try { if (debug) { cin = new BufferedReader(new InputStreamReader( new FileInputStream(INPATH))); } else { cin = new BufferedReader(new InputStreamReader(System.in)); } cout = new PrintWriter(new OutputStreamWriter(System.out)); // cout = new PrintWriter(OUTPATH); tok = new StreamTokenizer(cin); } catch (Exception e) { e.printStackTrace(); } } public static String next_str() { try { tok.nextToken(); if (tok.ttype == StreamTokenizer.TT_EOF) return null; else if (tok.ttype == StreamTokenizer.TT_NUMBER) { return String.valueOf((int)tok.nval); } else if (tok.ttype == StreamTokenizer.TT_WORD) { return tok.sval; } else return null; } catch (Exception e) { e.printStackTrace(); return null; } } public static int read_int() { String tmp_next_str = next_str(); return null==tmp_next_str ? -1 : Integer.parseInt(tmp_next_str); } public static long read_long() { return Long.parseLong(next_str()); } public static double read_double() { return Double.parseDouble(next_str()); } public static BigInteger read_big() { return new BigInteger(next_str()); } public static BigDecimal read_dec() { return new BigDecimal(next_str()); } }