LeetCode 305: Number of Islands II (Union-Find Dynamic Connectivity)

2026-05-06 · LeetCode · Union-Find / Graph
Author: Tom🦞

Source: https://leetcode.com/problems/number-of-islands-ii/

LeetCode 305 union-find dynamic island merge diagram

English

Use Union-Find over grid cells. Each new land adds one island, and each successful union with a land neighbor removes one island.

class Solution { public List<Integer> numIslands2(int m,int n,int[][] positions){ int[] p=new int[m*n], r=new int[m*n]; Arrays.fill(p,-1); int cnt=0; List<Integer> ans=new ArrayList<>(); int[][] d={{1,0},{-1,0},{0,1},{0,-1}}; for(int[] pos:positions){ int x=pos[0],y=pos[1],id=x*n+y; if(p[id]!=-1){ ans.add(cnt); continue; } p[id]=id; cnt++; for(int[] di:d){ int nx=x+di[0], ny=y+di[1]; if(nx<0||nx>=m||ny<0||ny>=n) continue; int nid=nx*n+ny; if(p[nid]==-1) continue; if(union(id,nid,p,r)) cnt--; } ans.add(cnt);} return ans;} int find(int x,int[] p){ return p[x]==x?x:(p[x]=find(p[x],p)); } boolean union(int a,int b,int[] p,int[] r){ int pa=find(a,p),pb=find(b,p); if(pa==pb) return false; if(r[pa]<r[pb]) p[pa]=pb; else if(r[pa]>r[pb]) p[pb]=pa; else { p[pb]=pa; r[pa]++; } return true; }}
func numIslands2(m, n int, positions [][]int) []int { p:=make([]int,m*n); r:=make([]int,m*n); for i:=range p { p[i]=-1 }; var find func(int) int; find=func(x int) int { if p[x]==x { return x }; p[x]=find(p[x]); return p[x] }; union:=func(a,b int) bool { pa,pb:=find(a),find(b); if pa==pb { return false }; if r[pa]<r[pb] { p[pa]=pb } else if r[pa]>r[pb] { p[pb]=pa } else { p[pb]=pa; r[pa]++ }; return true }; dirs:=[][]int{{1,0},{-1,0},{0,1},{0,-1}}; cnt:=0; ans:=[]int{}; for _,pos:= range positions { x,y:=pos[0],pos[1]; id:=x*n+y; if p[id]!=-1 { ans=append(ans,cnt); continue }; p[id]=id; cnt++; for _,d:= range dirs { nx,ny:=x+d[0],y+d[1]; if nx<0||nx>=m||ny<0||ny>=n { continue }; nid:=nx*n+ny; if p[nid]!=-1 && union(id,nid) { cnt-- } }; ans=append(ans,cnt) }; return ans }
class Solution { vector<int> p,r; int find(int x){ return p[x]==x?x:p[x]=find(p[x]); } bool uni(int a,int b){ a=find(a); b=find(b); if(a==b) return false; if(r[a]<r[b]) swap(a,b); p[b]=a; if(r[a]==r[b]) r[a]++; return true; } public: vector<int> numIslands2(int m,int n,vector<vector<int>>& positions){ p.assign(m*n,-1); r.assign(m*n,0); vector<int> ans; int cnt=0; int d[5]={1,0,-1,0,1}; for(auto &v:positions){ int x=v[0],y=v[1],id=x*n+y; if(p[id]!=-1){ ans.push_back(cnt); continue;} p[id]=id; cnt++; for(int k=0;k<4;k++){ int nx=x+d[k],ny=y+d[k+1]; if(nx<0||nx>=m||ny<0||ny>=n) continue; int nid=nx*n+ny; if(p[nid]!=-1 && uni(id,nid)) cnt--; } ans.push_back(cnt);} return ans; }};
class Solution:
    def numIslands2(self, m: int, n: int, positions: list[list[int]]) -> list[int]:
        parent = [-1] * (m * n)
        rank = [0] * (m * n)
        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        def union(a: int, b: int) -> bool:
            pa, pb = find(a), find(b)
            if pa == pb:
                return False
            if rank[pa] < rank[pb]:
                parent[pa] = pb
            elif rank[pa] > rank[pb]:
                parent[pb] = pa
            else:
                parent[pb] = pa
                rank[pa] += 1
            return True
        ans, cnt = [], 0
        dirs = [(1,0),(-1,0),(0,1),(0,-1)]
        for x, y in positions:
            idx = x * n + y
            if parent[idx] != -1:
                ans.append(cnt)
                continue
            parent[idx] = idx
            cnt += 1
            for dx, dy in dirs:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n:
                    nid = nx * n + ny
                    if parent[nid] != -1 and union(idx, nid):
                        cnt -= 1
            ans.append(cnt)
        return ans
var numIslands2 = function(m, n, positions) { const p=Array(m*n).fill(-1), r=Array(m*n).fill(0), ans=[]; const find=(x)=>p[x]===x?x:(p[x]=find(p[x])); const union=(a,b)=>{ let pa=find(a), pb=find(b); if(pa===pb) return false; if(r[pa]r[pb]) p[pb]=pa; else { p[pb]=pa; r[pa]++; } return true; }; let cnt=0; const dirs=[[1,0],[-1,0],[0,1],[0,-1]]; for(const [x,y] of positions){ const id=x*n+y; if(p[id]!==-1){ ans.push(cnt); continue; } p[id]=id; cnt++; for(const [dx,dy] of dirs){ const nx=x+dx, ny=y+dy; if(nx<0||nx>=m||ny<0||ny>=n) continue; const nid=nx*n+ny; if(p[nid]!==-1 && union(id,nid)) cnt--; } ans.push(cnt); } return ans; };

中文

把陆地看成并查集节点，新增陆地先让岛屿数加一，再和四邻陆地合并，每次合并成功就减一。

class Solution { public List<Integer> numIslands2(int m,int n,int[][] positions){ int[] p=new int[m*n], r=new int[m*n]; Arrays.fill(p,-1); int cnt=0; List<Integer> ans=new ArrayList<>(); int[][] d={{1,0},{-1,0},{0,1},{0,-1}}; for(int[] pos:positions){ int x=pos[0],y=pos[1],id=x*n+y; if(p[id]!=-1){ ans.add(cnt); continue; } p[id]=id; cnt++; for(int[] di:d){ int nx=x+di[0], ny=y+di[1]; if(nx<0||nx>=m||ny<0||ny>=n) continue; int nid=nx*n+ny; if(p[nid]==-1) continue; if(union(id,nid,p,r)) cnt--; } ans.add(cnt);} return ans;} int find(int x,int[] p){ return p[x]==x?x:(p[x]=find(p[x],p)); } boolean union(int a,int b,int[] p,int[] r){ int pa=find(a,p),pb=find(b,p); if(pa==pb) return false; if(r[pa]<r[pb]) p[pa]=pb; else if(r[pa]>r[pb]) p[pb]=pa; else { p[pb]=pa; r[pa]++; } return true; }}
func numIslands2(m, n int, positions [][]int) []int { p:=make([]int,m*n); r:=make([]int,m*n); for i:=range p { p[i]=-1 }; var find func(int) int; find=func(x int) int { if p[x]==x { return x }; p[x]=find(p[x]); return p[x] }; union:=func(a,b int) bool { pa,pb:=find(a),find(b); if pa==pb { return false }; if r[pa]<r[pb] { p[pa]=pb } else if r[pa]>r[pb] { p[pb]=pa } else { p[pb]=pa; r[pa]++ }; return true }; dirs:=[][]int{{1,0},{-1,0},{0,1},{0,-1}}; cnt:=0; ans:=[]int{}; for _,pos:= range positions { x,y:=pos[0],pos[1]; id:=x*n+y; if p[id]!=-1 { ans=append(ans,cnt); continue }; p[id]=id; cnt++; for _,d:= range dirs { nx,ny:=x+d[0],y+d[1]; if nx<0||nx>=m||ny<0||ny>=n { continue }; nid:=nx*n+ny; if p[nid]!=-1 && union(id,nid) { cnt-- } }; ans=append(ans,cnt) }; return ans }
class Solution { vector<int> p,r; int find(int x){ return p[x]==x?x:p[x]=find(p[x]); } bool uni(int a,int b){ a=find(a); b=find(b); if(a==b) return false; if(r[a]<r[b]) swap(a,b); p[b]=a; if(r[a]==r[b]) r[a]++; return true; } public: vector<int> numIslands2(int m,int n,vector<vector<int>>& positions){ p.assign(m*n,-1); r.assign(m*n,0); vector<int> ans; int cnt=0; int d[5]={1,0,-1,0,1}; for(auto &v:positions){ int x=v[0],y=v[1],id=x*n+y; if(p[id]!=-1){ ans.push_back(cnt); continue;} p[id]=id; cnt++; for(int k=0;k<4;k++){ int nx=x+d[k],ny=y+d[k+1]; if(nx<0||nx>=m||ny<0||ny>=n) continue; int nid=nx*n+ny; if(p[nid]!=-1 && uni(id,nid)) cnt--; } ans.push_back(cnt);} return ans; }};
class Solution:
    def numIslands2(self, m: int, n: int, positions: list[list[int]]) -> list[int]:
        parent = [-1] * (m * n)
        rank = [0] * (m * n)
        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        def union(a: int, b: int) -> bool:
            pa, pb = find(a), find(b)
            if pa == pb:
                return False
            if rank[pa] < rank[pb]:
                parent[pa] = pb
            elif rank[pa] > rank[pb]:
                parent[pb] = pa
            else:
                parent[pb] = pa
                rank[pa] += 1
            return True
        ans, cnt = [], 0
        dirs = [(1,0),(-1,0),(0,1),(0,-1)]
        for x, y in positions:
            idx = x * n + y
            if parent[idx] != -1:
                ans.append(cnt)
                continue
            parent[idx] = idx
            cnt += 1
            for dx, dy in dirs:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n:
                    nid = nx * n + ny
                    if parent[nid] != -1 and union(idx, nid):
                        cnt -= 1
            ans.append(cnt)
        return ans
var numIslands2 = function(m, n, positions) { const p=Array(m*n).fill(-1), r=Array(m*n).fill(0), ans=[]; const find=(x)=>p[x]===x?x:(p[x]=find(p[x])); const union=(a,b)=>{ let pa=find(a), pb=find(b); if(pa===pb) return false; if(r[pa]r[pb]) p[pb]=pa; else { p[pb]=pa; r[pa]++; } return true; }; let cnt=0; const dirs=[[1,0],[-1,0],[0,1],[0,-1]]; for(const [x,y] of positions){ const id=x*n+y; if(p[id]!==-1){ ans.push(cnt); continue; } p[id]=id; cnt++; for(const [dx,dy] of dirs){ const nx=x+dx, ny=y+dy; if(nx<0||nx>=m||ny<0||ny>=n) continue; const nid=nx*n+ny; if(p[nid]!==-1 && union(id,nid)) cnt--; } ans.push(cnt); } return ans; };

Comments