z1x2c3   5년 전

다른분들 코드를 보면,

아래처럼 하신 분들이 꽤 있더라구요. SCC순서에 따라 참/거짓을 결정하는데, 어떻게 생각해야될 지 잘모르겠습니다.

rhs0266   5년 전

i번 정점을 차용하는 것이 가지는 의미는 "x_i 는 true다", neg[i]번 정점을 차용하는 것이 가지는 의미는 "x_i는 false다", 간선 u->v 가 가지는 의미는 "u번 정점을 채용한다면 v번 정점도 채용해야만 한다" 입니다.


출력문만 보면, i번 정점에서 neg[i]번 정점으로 가는 길이 있다면 scc[i]는 scc[neg[i]] 보다 큰 상황이라고 보이는데요. 이를 미뤄본다면 i번 정점을 차용한다면 neg[i]번 정점도 차용해야 하고, 이는 곧 모순을 발생 시키기 때문에 neg[i]번 정점만 차용해야 한다는 것입니다.

반대로, neg[i]번 정점에서 i번 정점으로 가는 길이 있따면, scc[i]는 scc[neg[i]]보다 작은 상황이며, neg[i]번 정점을 차용한다면 i번 정점도 차용해야 하기 때문에 모순이 발생되므로 i번 정점만 차용해야 합니다. 이를 한 줄로 짧게 저런 식으로 처리한 것으로 보입니다.

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