[Algorithm] 집합의 표현

[hwangJi-dev]

💬 문제

https://www.acmicpc.net/problem/1717

💬 Idea

• union-find를 이용하여 문제를 풀이했다. (공통 조상 찾기와 유사)

💬 풀이

import Foundation

func solution1717() {
    let nm = readLine()!.components(separatedBy: .whitespaces).map({ Int($0)! })
    var parent = [Int](0...nm[0])
    
    func find(_ b: Int) -> Int {
        if b != parent[b] {
            parent[b] = find(parent[b])
        }
        return parent[b]
    }
    
    func union(_ a: Int, _ b: Int) {
        let a = find(a)
        let b = find(b)
        
        if a >= b {
            parent[a] = b
        } else {
            parent[b] = a
        }
    }
    
    for _ in 1...nm[1] {
        let cal = readLine()!.components(separatedBy: .whitespaces).map({ Int($0)! })
        let a = cal[1]
        let b = cal[2]
        
        if cal[0] == 0 {
            union(a, b)
        } else {
            if find(a) == find(b) {
                print("YES")
            } else {
                print("NO")
            }
        }
    }
}