글 읽기 - 11281 true or false

도저히 이해가 가지 않는 부분이 있어 질문을 남기게 되었습니다.

다른 분들의 답을 살펴보면 x와 -x의 SCC 순서(누가 먼저 SCC로 형성되었는지)를 비교하여 x의 boolean 값을 결정하던데

주어진 예시같은 경우

1과 -1, 2와 -2 사이에는 순서라 할 것이 없습니다. (1과 -1, 2와 -2 사이에 서로를 향한 path가 존재하지 않습니다.)

따라서 어떤 노드를 먼저 방문하냐에 따라 각각의 SCC 순서가 결정이 될 것인데,

그렇게 되면 1이 true, 2가 false인 상황이 나올 수 있지 않을까요? (이러한 경우 예제의 식은 거짓이 됩니다.)

간단히 SCC 순서 비교로만 변수의 참/거짓을 결정할 수 있는지 궁금합니다!

> 어떤 노드를 먼저 방문하냐에 따라 각각의 SCC 순서가 결정이 될 것인데

는 맞지만

> 그렇게 되면 1이 true, 2가 false인 상황이 나올 수 있지 않을까요?

는 아닙니다. 그런 상황은 나올 수 없습니다. 한번 그래프를 그려 보고 이것 저것 해 보시기 바랍니다.

답변 감사합니다!

koosaga 님이 말씀하신 것처럼 예시 그래프를 가지고 해보니 1이 true, 2가 false 인 경우는 나올 수 없네요.

하지만 일반적으로 이런 경우는 존재하지 않는다는 엄밀한 증명같은게 있을까요?

네 엄밀한 증명이 있는데 지금은 기억이 잘 나지 않습니다.. ㅠㅠ

넵넵 감사합니다!!

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

Baekjoon Online Judge