백준 - 거짓말 (1043)

let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
let (N, M) = (input[0], input[1])
let truth = readLine()!.split(separator: " ").map{ Int(String($0))! }
var answer = 0
var party = [[Int]]()
var parent = Array(0...N+1)

for _ in 0..<M {
    let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
    for i in stride(from: 1, to: input.count, by: 1) {
        union(input[1], input[i])
    }
    party.append(input)
}

for now in party {
    var flag = true
    for i in stride(from: 1, to: truth.count, by: 1) {
        if checkSame(now[1], truth[i]) {
            flag = false
            break
        }
    }
    if flag {
        answer += 1
    }
}

print(answer)

// 유니온 파인드 관련 함수
func union(_ a: Int, _ b: Int) {
    let aParent = find(a)
    let bParent = find(b)
    
    if aParent < bParent {
        parent[bParent] = aParent
    } else {
        parent[aParent] = bParent
    }
}

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

func checkSame(_ a: Int, _ b: Int) -> Bool {
    return find(a) == find(b)
}

• 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 듣는 경우도 체크해야 한다.
  • → 유니온 파인드를 사용해서 파티에 참여한 사람들을 같은 집합으로 묶어준다.
• 파티 참여자마다 union 연산을 수행한 후에 각 파티마다 진실을 알고 있는 사람들과 같은 집합에 있는지 확인한다. 같은 집합에 있지 않다면 파티 개수를 1 더해준다.