만득

코딩 공부 정리용

​

© 2021. All rights reserved.

백준 20040 사이클 게임

23 Jun 2021

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

총 n개의 정점이 있을 때 두 정점을 잇는 간선들이 m개 주어진다고 하자. 만약 간선을 긋는 과정에서 사이클이 발생했다면 몇번째 차례인지 출력하고 만약 m개를 다 긋는 동안 사이클이 발생하지 않았다면 0을 출력하는 문제이다. 사이클의 여부를 파악할 때는 union find를 사용하면 간단하게 표현할 수 있다. 만약 간선을 그으려고 할 때 양 끝점이 같은 집합에 속해있다면 해당 간선을 긋는 행위는 사이클을 발생시키는 것이 된다. 따라서 간선이 주어질 때마다 union이 성공하는지 실패하는지를 확인해 결과를 출력해주면 된다.

struct DisjointSet {
    var arr:[Int]
    init(_ n: Int) {
        arr = [Int](0..<n)
    }
    mutating func findRoot(_ n: Int) -> Int {
        if arr[n] == n {
            return n
        }
        else {
            let root = findRoot(arr[n])
            arr[n] = root
            return root
        }
    }
    mutating func union(_ a: Int, _ b: Int) -> Bool {
        let rootA = findRoot(a), rootB = findRoot(b)
        if rootA == rootB {
            return false
        }
        else if rootA < rootB {
            arr[rootB] = rootA
        }
        else {
            arr[rootA] = rootB
        }
        return true
    }
}

let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n =  nm[0], m = nm[1]
var disjointSet = DisjointSet(n)
var result = 0
for i in 1...m {
    let node = readLine()!.split(separator: " ").map{Int(String($0))!}
    if !disjointSet.union(node[0], node[1]) {
        result = i
        break
    }
}
print(result)

Related posts