SCC. [3648]

[1. 문제 설명]

---

[2. 풀이 접근]

오답이었던 방식

• 1 을 포함하는 경우는 x₁ 이 반드시 true 이어야 하므로 무시한다. (true /  false 중 아무거나 와도 된다.)
• -1 을 포함하는 경우는, 해당 절을 true 로 만들어야 하므로, x_i 에 오는 값을 정할 수 있다.
  => (true 또는 false 중 하나가 되야 한다.)
• 이때, x_i 에 이미 값이 할당되어있고, 이번에 할당 할 값 과 다르면 전체 식을 true 로 만들 수 없다.
  => 앞에 절을 참으로 한 값을 변경하면, 이번 절이 참이 되나,
  => 그 전의 절은 false 가 되므로 전체 식을 true 로 할 수 없다.
  => "no" 를 출력한다.
• 논리식에 대한 그래프를 만들고 난 뒤, scc 로 묶는다.
• n 과 -n 이 같은 scc 에 있으면, "no" 를 출력한다.
• 모든 n 과 -n 이 다른 scc 에 있으면, "yes" 를 출력한다.

반례를 모르겠다.

아마, x_i 와 -1 이 같이 있어, x_i고정된 값을 주었는데, 실제 해를 구한 것과 다른 경우 => 모순 => "no" 출력해야함
=> x_i 가 다른 절 에는 포함되서 해를 구해 볼 수 있다면,

=> 이 경우를 체크안해서?

---

올바른 접근

• x1 이 반드시 참이 되어야 하는 절이 필요하다.
• 전체 논리식에 (x₁ ∨ x₁) 을 추가한다.
• 이후, 2-SAT 와 같은 방식으로 풀이한다.

---

[3. 코드]