글 읽기 - [파이썬] 1043번 거짓말 union-find 5% 틀렸습니다.

ebbunnim 2년 전 0

각 파티를 노드로 잡고,서로 다른 노드간에 겹치는 숫자가 있다면 union해줍니다.

이때 parent를 find에서 갱신해주게 되는데, 나중에는 root parent로 잡은 원소만 확인하면 거짓말을 할 수 있는지 없는지를 판단할 수 있도록 node 정보를 합쳐주었습니다.

게시판의 모든 테케가 다 맞는데 5%에서 틀렸습니다가 뜹니다. ㅠㅠ

def union(a,b): # a,b는 노드 번호임
    a=find(a)
    b=find(b)
    if a<b:
        parents[b]=a
        nodes[a]|=nodes[b]
    else:
        parents[a]=b
        nodes[b]|=nodes[a]

def find(x): # 속한 부모 찾아 나서기
    if parents[x]!=x:
        parents[x]=find(parents[x])
    return parents[x]

if __name__ == '__main__':
    N,M=map(int,input().split())
    T=list(map(int,input().split()))
    Tn,Tset=T[0],set(T[1:])
    parents = list(range(M))
    nodes=[set()]*M
    graph=[[] for _ in range(M)]
    for i in range(M):
        P=list(map(int,input().split()))
        Pn,Plist=P[0],P[1:]
        nodes[i]=set(Plist)

    for i in range(M):
        for j in range(M):
            if i==j:
                continue
            if nodes[i]&nodes[j]: # 교집합의 원소가 있다면
                union(i,j)

    cnt=0
    for group in set(parents):
        if nodes[group]&Tset:
            continue
        cnt+=parents.count(group)
    print(cnt)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[파이썬] 1043번 거짓말 union-find 5% 틀렸습니다.

ebbunnim 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말