728x90
1043번: 거짓말
지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게
www.acmicpc.net
분석
https://www.acmicpc.net/board/view/112226
2가 1에 의해 진실을 알게 되었기 때문에.가 아니라
1번 파티에 지민이가 참석하였을 때, 1번 사람이 있기 때문에 지민이는 진실을 이야기 할 수 밖에 없고,
1번 파티에 참석한 2번 사람은 해당 사실에 대해 알게 되었기 때문에,
다음 파티인 2번에 지민이가 참석 하였기 때문에, 1번 파티에서 진실을 들은 2번이 있기 때문에 지민이는 또 진실을 이야기할 수 밖에 없고, 마지막 파티에 가서도 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
# i번째 파티의 사람 (같이 있으면 사실/과장 통일) → 대표노드
firstPerson=party[i][0]
# 진실을 아는 사람들의 수만큼 반복
for j in range(len(p)):
# 각 파티의 대표 노드와 진실을 아는 사람들의 대표 노드가 같다면 과장 할 수 없음
# print(find(firstPerson))
if find(firstPerson)==find(p[j]):
isPossible=False
break
if isPossible:
result+=1
print(result)
728x90