[BOJ]1043번: 거짓말

 

www.acmicpc.net/problem/1043

---

지민이가 거짓말을 했다는 걸 아는 사람과 같은 컴포넌트 내에 있는 사람은 모두 제외하면 됩니다.

 

이걸 구하는 방식은 아래와 같습니다.

 

1. 맨 처음 입력받은 파티 정보로 지민이가 거짓말을 하는 걸 아는 사람들과 바로 연결되어 있는 사람들을 구합니다.

 

2. 그 후에 플로이드 알고리즘이 N^3으로 i -> j의 연결관계를 1~k까지 중간지점을 경유해서 구하는 것처럼,

 

N번 루프 밖에 루프를 돌면서 (한 사람이 다른 사람과 관계를 맺을 때 최대 걸리는 길이는 N-1번)

i,j가 연결관계에 있는데, 둘 중 한명이라도 거짓말을 안다면 나머지 한 명도 그 사실을 알도록 체크해줍니다.

 

3. 2번과정을 마친 후 파티 정보를 순회하면서 파티 내에 거짓말 사실을 아는 사람 여부를 체크하면 됩니다.

---

코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ1043.cc