백준 1043번 거짓말(swift) [G4]

유니온 파인드

• 그래프에서 뿌리 찾기 ( 연결된 집합인지 아닌지 판단 )

생각회로

• 전염병 처럼 진실을 아는 사람과 같은 파티에 가면, 그 파티에 참여한 모든 사람이 진실을 알게된다.

• 예제
  3 7
  1 1
  3 1 2 3
  3 3 4 5
  3 5 6 7
  이 경우 ,
  1 -> 2,3
  3 -> 4,5
  5 -> 6,7 모두 전염한다. 그래서 답은 0.

• Union-find로 해결했다.
  모두 -1로 초기화, 진실을 아는 경우에는 부모를 0으로 통일한다.

주의사항

• 배운 점 :
  
  코드 이쁘게 쓰기.

소스코드

import Foundation


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

func merge(_ a:Int, _ b:Int){
    let x = find(a)
    let y = find(b)
    
    if x == y {
        return
    }
    
    if x == 0 || y == 0{
        p[a] = 0
        p[b] = 0
        return
    }
    
    if x < y {
        p[y] = x
    }else{
        p[x] = y
    }
    
}


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

input = readLine()!.split(separator: " ").map{Int(String($0))!}
if input[0] == 0{
    print(M)
    exit(0)
}

input.removeFirst()
var liar = input
var party = [[Int]]()
var p = Array(repeating: -1, count: N+1)

for l in liar{
    p[l] = 0
}

for i in 0..<M{
    party.append(readLine()!.split(separator: " ").map{Int(String($0))!})
    
    party[i].removeFirst()
    party[i].sort()
    
    if party[i].count < 2{
        continue
    }
    
    for j in party[i]{
        merge(party[i][0], j)
    }
}

for _ in 0..<N{
    for i in 0..<M{
        if party[i].count < 2{
            continue
        }
        for j in party[i]{
            merge(party[i][0], j)
        }
    }
}

var ret = 0

for thisParty in party{
    var canLie = true
    for person in thisParty{
        if p[person] == 0{
            canLie = false
            break;
        }
    }
    if canLie{
        ret += 1
    }
}
print(ret)