547. Friend Circles

class Solution {
    func findCircleNum(_ M: [[Int]]) -> Int {
        guard M.count > 1 else { return  M.count}
        let n = M.count
        let uf = UnionFind(n)
        var res = 0
        for i in stride(from: 0, to : n  , by: 1 ){
            for j in stride(from: i + 1 , to : n , by: 1 ){
                if i == j {continue}
                if M[i][j] == 1 {
                    uf.union(i, j)
                }
            }
        }

        return uf.count
    }
}

class UnionFind{
    var father : [Int]
    var count : Int
    init(_ n : Int){
        count = n
        father = [Int](repeating: 0 , count : n)
        for i in 0 ..< n {
            father[i] = i
        }
    }
    func find(_ x : Int) -> Int{
        if father[x] == x {
            return x
        }
        let root_x = find(father[x])
        father[x] = root_x
        return root_x
    }

    func union(_ x : Int, _ y : Int){
        let root_x = find(x)
        let root_y = find(y)
        if root_x == root_y {return }
        count -= 1
        father[root_x] = root_y
    }
}