B. Deduction

$N$개의 명제 $S_1, S_2, ..., S_N$이 있고, 명제들 사이의 관계가 주어졌을 때 모순의 여부를 판별하는 문제다.

명제는 참 또는 거짓일 수 있으며, 우리는 어떤 명제 $S_i$에 대해 참이라고 확신하거나, 참인지 거짓인지 모르는 경우 두 가지 상황이 있다. 관계는 세 가지 종류로 주어진다. 이 종류를 자세히 살펴보면 우리는 명제가 참인지 거짓인지 모를 때, 거짓이라고 가정해도 모순 판별 여부에 아무런 영향이 없음을 알 수 있다. 쉽게 말하자면, 참이라는 확신이 없을 때에는 거짓이라고 생각해도 무관하다.

위와 같은 사실을 알았을 때, 우리는 1번 종류와 3번 종류 관계를 잘 이용해서 참이라고 확신할 수 있는 명제들을 추려내면 된다. 참이라고 확신할 수 있는 명제들을 추려낸 뒤, 2번 종류 관계에서 모순이 있는지 확인하면 문제가 해결 된다. 총 시간복잡도는 $O(N^2)$ 이다.

#include <stdio.h> #include <vector> using namespace std; typedef vector<int> arr; int T, N, M1, M2, M3; bool A[1501]; int cnt[1501]; arr one, con[1501]; vector <arr> two, three; void dfs(int n) { if (A[n]) return; A[n] = 1; for (int t: con[n]){ if (++cnt[t] == three[t].size()-1) dfs(three[t].back()); } } int main() { int i, j, k; for (scanf("%d", &T);T--;){ scanf("%d%d%d%d", &N, &M1, &M2, &M3); one.clear(); two.clear(); three.clear(); for (i=1;i<=N;i++) A[i] = 0, con[i].clear(); for (i=0;i<M1;i++) scanf("%d", &k), one.push_back(k); for (i=0;i<M2;i++){ arr tmp; for (scanf("%d", &j);j--;) scanf("%d", &k), tmp.push_back(k); two.push_back(tmp); } for (i=0;i<M3;i++){ arr tmp; cnt[i] = 0; for (scanf("%d", &j);j--;) scanf("%d", &k), con[k].push_back(i), tmp.push_back(k); scanf("%d", &k), tmp.push_back(k); three.push_back(tmp); } for (int t: one) dfs(t); bool ans = 1; for (arr &a: two){ bool sw = 0; for (int t: a) if (!A[t]){ sw = 1; break; } if (!sw){ ans = 0; break; } } puts(ans?"YES":"NO"); } }