https://algospot.com/judge/problem/read/MEETINGROOM


위의 종만북 투샛 문제에서


답이 없을경우 IMPOSSIBLE 을 출력해야되는데


책에서는 이거를


X와 Y가 같은 SCC에 속한다면 !X 와 !Y 도 같은 SCC에 속하게 되는 것이지요.


그러므로 SCC 들 간에도 원래의 함의 그래프와 같은 1:1 대응관계가 존재하고


(주석: 물론 한변수를 표현하는 두 정점이 한 SCC 안에 들어잇는 경우에는 1:1관계가 성립하지 않을겁니다. 하지만 이경우에는 답이 존재하지 않음을 이미 알고 있으니 이런 경우는 미리 걸러내면 됩니다)


, 한 SCC가 참이라면 그의 반대 SCC는 항상 거짓이어야 함을 알수 있습니다.



라고 써있는데. 


책에는 그냥 저렇게만 나오고 슥~ 지나감


암튼 위에서 말한 "한 변수를 표현하는 두 정점" 이란


1. [A회의] 열림 (이하 변수 A라고 부름)

2. [A회의] 안열림 (이하 변수 !A)


이거 자너? 근데 어떻게 "저 두개가 같은 scc 에 들어있는지만 체크하면 답의 존재여부 검사가 끝남" 가 성립하는거임?


물론 같은 SCC에 속해있으면 당연히 참거짓 값도 같을테니 "IMPOSSIBLE" 출력해야되긴 하는데


서로 다른 SCC에 묶여 있더라도 답이 존재 할수 없는 경우도 있지 않음?


예를들어 A와 !A가 다른 SCC 이지만,


두 SCC의 진리값이 둘다 참이 거나 (A와 !A가 참이 되므로 모순이 발생)


둘다 False 이거나 (A 와 !A 둘다 False)


일때 답이 존재하지 않잖아. 결국 중요한건 두 변수가 속해있는 SCC의 참거짓 값이 중요한거아님?


뭔가 이거랑 관련된 베이스가 깔려있어야 되나? 아니면 그냥 직관적으로 딱보고 알수있는거임? 나는 둘다 해당이 안되서 모르겠음;;


어떻게 딱보고 "한변수를 표현하는 두 정점이 한 SCC 안에 들어잇는 경우" 만 체크하면 된다는게 바로나오는지..