Swift solution - Union Find, DFS, BFS


  • 0
    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
        }
    }
    

Log in to reply
 

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