Swift solution - Union Find, DFS, BFS

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

let n = M.count
let unionFind = UnionFind(n)

for i in 0..<(n - 1) {
for j in (i + 1)..<n {
if M[i][j] == 1 {
unionFind.union(i, j)
}
}
}
return unionFind.getCount()
}

func findCircleNum_DFS(_ M: [[Int]]) -> Int {
if M.count == 0 || M[0].count == 0 {
return 0
}

var visited = [Int](repeatElement(0, count: M.count ))
var count = 0

for i in 0..<M.count {
if visited[i] == 0 {
DFS(M, &visited, i)
count += 1
}
}

return count
}

func DFS(_ M: [[Int]], _ visited: inout [Int], _ i: Int) {
for j in 0..<M.count {
if M[i][j] == 1 && visited[j] == 0 {
visited[j] = 1
DFS(M, &visited, j)
}
}
}

func findCircleNum_BFS(_ M: [[Int]]) -> Int {
if M.count == 0 || M[0].count == 0 {
return 0
}

var M = M
var count = 0

for i in 0..<M.count {
if M[i][i] == 1 {
count += 1
BFS(i, &M)
}
}

return count
}

func BFS(_ student: Int, _ M: inout [[Int]]) {
var queue = [Int]()

queue.append(student)
while !queue.isEmpty {
let size = queue.count
for _ in 0..<size {
let j = queue.removeFirst()
M[j][j] = 2
for k in 0..<M[0].count {
if M[j][k] == 1 && M[k][k] == 1 {
queue.append(k)
}
}
}
}
}
}

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

public init(_ n: Int) {
self.count = n
self.parent = [Int](repeatElement(0, count: n))
self.rank = [Int](repeatElement(0, count: n))
for i in 0..<n {
self.parent[i] = i
self.rank[i] = 0
}
}

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
}
if self.rank[i] < self.rank[j] {
self.parent[i] = j
} else if self.rank[i] > self.rank[j] {
self.parent[j] = i
} else {
self.parent[j] = i
self.rank[i] += 1
}
self.count -= 1
}
}
``````

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