(1043) 거짓말 (UnionFind)

분석하다

https://www.acmicpc.net/board/view/112226
2가 1에 의해 진실을 알게 되었기 때문이 아닙니다.
지민이 1호 파티에 참석하면 1호가 있기 때문에 지민은 사실대로 말할 수밖에 없다.
파티 1에 참석한 2는 그 사실을 알게 되어서
다음 파티인 2번 지민이 참석한 이후로 2번이 1번 파티에서 진실을 들었기 때문에 지민은 다시 진실을 말할 수밖에 없었고, 마지막 파티에서도 2번 파티에서 4번이 진실을 들었다. , 다시 진실을 말할 수밖에 없다
절대 과장된 이야기를 할 수 없기 때문에 0이 되어야 할 것 같습니다.

https://www.acmicpc.net/board/view/93121
“물론 한 쪽에서는 진실을, 다른 쪽에서는 과장을 들을 때요.”
입력은 위에서 아래로 순차적으로 받는데 이때 DSU 알고리즘을 사용하는데 지민이 거짓말을 할 수 있는지 계산하면 안 된다.
모든 파티원에 대해 DSU를 실행한 후 다시 모든 파티원에 대해 거짓말이 가능한지 확인해야 합니다.

설명

"""
사람수 n, 파티수 m
진실아는 사람정보 1 1
파티정보 m줄 참여자수 참여자번호

거짓말 할 수 있는 파티 개수 최댓값
"""
result=0

#사람수 n, 파티수 m
n,m=map(int,input().split())

# 진실을 아는 사람 정보
p=list(map(int, input().split()))
t=p(0) # 진실을 아는 사람 수
del p(0)

# 파티정보
party=(() for _ in range(m))
for i in range(m):
    party(i)=list(map(int,input().split()))
    del party(i)(0)

# 대표노드  리스트
arr=(0)*(n+1)
for i in range(1, n+1):
    arr(i)=i


def find(a): # 대표노드 찾기
    if a == arr(a):
        return a
    else:
        arr(a) = find(arr(a))
        return arr(a)

def union(a, b):
    a = find(a)
    b = find(b)
    if a != b:
        arr(b) = a

# 각 파티에 참여한 사람들을 1개의 그룹으로 만들기
for i in range(m):
    firstPerson=party(i)(0)
    for j in range(1, len(party(i))):
        union(firstPerson, party(i)(j))
    # print(arr)


# 각 파티의 대표 노드와 진실을 아는 사람들의 대표 노드가 같다면 과장 할 수 없음
for i in range(m):
    isPossible=True
    firstPerson=party(i)(0)

    for j in range(len(p)):
        if find(firstPerson)==find(p(j)):
            isPossible=False
            break
    if isPossible:
        result+=1

print(result)​