# Swift solution - Union Find, DFS

• ``````class Solution {
func numIslands_UnionFind(_ grid: [[Character]]) -> Int {
if grid.count == 0 || grid[0].count == 0 {
return 0
}

let m = grid.count
let n = grid[0].count
let uf = UnionFind2(m, n, grid)

for i in 0..<m {
for j in 0..<n {
if grid[i][j] == "0" {
continue
}
let p = i * n + j
var q = 0
if i > 0 && grid[i - 1][j] == "1" {
q = p - n
uf.union(p, q)
}
if i < m - 1 && grid[i + 1][j] == "1" {
q = p + n
uf.union(p, q)
}
if j > 0 && grid[i][j - 1] == "1" {
q = p - 1
uf.union(p, q)
}
if j < n - 1 && grid[i][j + 1] == "1" {
q = p + 1
uf.union(p, q)
}
}
}

return uf.getCount()
}

func numIslands_DFS(_ grid: [[Character]]) -> Int {
if grid.count == 0 {
return 0
}

let n = grid.count
let m = grid[0].count
var count = 0
var grid = grid

for i in 0..<n {
for j in 0..<m {
if grid[i][j] == "1" {
DFS(&grid, i, j)
count += 1
}
}
}

return count
}

func DFS(_ grid: inout [[Character]], _ i: Int, _ j: Int) {
let n = grid.count
let m = grid[0].count

if i < 0 || i >= n || j < 0 || j >= m || grid[i][j] != "1" {
return
}

grid[i][j] = "0"
DFS(&grid, i + 1, j)
DFS(&grid, i - 1, j)
DFS(&grid, i, j + 1)
DFS(&grid, i, j - 1)
}
}

public class UnionFind {
var parent: [Int]
var count: Int

public init(_ m: Int, _ n: Int, _ grid: [[Character]]) {
self.count = 0
for i in 0..<m {
for j in 0..<n {
if grid[i][j] == "1" {
self.count += 1
}
}
}

self.parent = [Int](repeatElement(0, count: m * n))
for i in 0..<(m * n) {
self.parent[i] = i
}
}

public func find(_ p: Int) -> Int {
var p = p
while p != self.parent[p] {
self.parent[p] = self.parent[self.parent[p]]
p = self.parent[p]
}
return p
}

public func getCount() -> Int {
return self.count
}

public func connected(_ p: Int, _ q: Int) -> Bool {
return find(p) == find(q)
}

public func union(_ p: Int, _ q: Int) {
let i = find(p)
let j = find(q)

if i == j {
return
}
self.parent[i] = j
self.count -= 1
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.