백준 17352번 여러분의 다리가 되어 드리겠습니다! - 스위프트(Swift) 풀이

1. 모든 다리에 대해 다리로 이어진 두 섬을 union 한다.
2. 1번 섬과 이어지지 않은 섬, 즉 find(i) ≠ find(1)인 섬을 찾아 (1, i)를 출력한다.

---

1. 모든 다리에 대해 다리로 이어진 두 섬을 union 한다.

 다리로 이어진 두 섬은 왕복할 수 있다. 1 - 2가 연결되어 있고, 1 - 3이 연결되어 있으면 2 - 3으로도 갈 수 있다. union 연산과 같다.

 

2. 1번 섬과 이어지지 않은 섬, 즉 find(i) ≠ find(1)인 섬을 찾아 (1, i)를 출력한다.

 어떤 두 섬이든 다리로 왕복할 수 있으려면 1번 섬에서도 어느 섬으로든 갈 수 있어야 한다. 따라서 1번 섬과 부모가 다른 섬을 찾아 출력해주면 된다. 1번 섬이 아니더라도 아무 섬이나 하나 기준으로 잡고, 그 섬과 연결되지 않은 섬을 찾아 출력해주면 된다.

 

---

import Foundation

var parents = [Int]()
var rank = Array(repeating: 1, count: 300_001)

func initParents(_ n: Int) {
    parents = (0...n).map{ $0 }
}

func find(_ n: Int) -> Int {
    if parents[n] == n { return n }
    
    parents[n] = find(parents[n])
    
    return parents[n]
}

func union(a: Int, b: Int) {
    var pa = find(a), pb = find(b)
    
    if pa == pb { return }
    
    if rank[pa] < rank[pb] { swap(&pa, &pb) }
    parents[pb] = pa
    rank[pa] += rank[pb]
}

func solution() {
    let N = Int(readLine()!)!
    
    initParents(N)
    
    for _ in 0..<N-2 {
        let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
        let A = input[0]
        let B = input[1]
        
        union(a: A, b: B)
    }
    
    for i in 2...N {
        if find(1) != find(i) {
            print(1, i)
            break
        }
    }
}

solution()