[BOJ 19703] 실험

문제

---

https://www.acmicpc.net/problem/19703

풀이

---

단순한 2-sat 문제처럼 보임에도 불구하고 다이아인 이유는 조건 1 때문이다.

각 그룹의 모든 구성원 쌍 x, y에 대해, 단순히 x $ \rightarrow $ !y, y $ \rightarrow $ !x 간선을 추가해 준다면 최대 $ A^2 = 25 \times 10^{10} $개의 간선이 만들어지므로 간선만 추가하다가 TLE가 뜬다.

그러므로 이를 O(A), 혹은 각 그룹의 크기의 선형 시간 내에 해결해야 한다.

이 테크닉은 jh05013님의 블로그에 잘 설명되어 있다.

또한 python은 TLE가 떠 C++로 제출했다.

코드

---

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;
int MAX = 1200010;
int idx, scc_num;
stack<int> S;
vector<int> visit(MAX), scc_idx(MAX), finish(MAX);
vector<vector<int>> graph(MAX), group(100010);

int dfs(int cur) {
	S.push(cur);
	visit[cur] = idx;
	int low = idx;
	idx += 1;

	for (int nxt : graph[cur]) {
		if (not visit[nxt]) {
			low = min(low, dfs(nxt));
		}
		else if (not finish[nxt]) {
			low = min(low, visit[nxt]);
		}
	}

	if (low == visit[cur]) {
		while (true) {
			int top = S.top();
			S.pop();
			finish[top] = 1;
			scc_idx[top] = scc_num;
			if (cur == top) {
				break;
			}
		}
		scc_num += 1;
	}
	return low;
}

int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios::sync_with_stdio(false);

    int n, m, a, b;
	cin >> n >> m >> a >> b;
	int k = 2 * n + 2 * a + 1;

    for (int i = 0; i < a; i++) {
        int x, y;
        cin >> x >> y;
        group[y].push_back(x);
    }

    int idx = 2 * n;
    for (int i = 1; i < m + 1; i++) {
        for (int j = 0; j + 1 < group[i].size(); j++) {
            int x = group[i][j];
            int y = group[i][j + 1];
            graph[2 * x - 1].push_back(idx + 2 * j + 1);
            graph[idx + 2 * j + 1].push_back(idx + 2 * j + 3);
            graph[idx + 2 * j + 1].push_back(2 * y);
            graph[idx + 2 * j + 2].push_back(2 * x);
            graph[idx + 2 * j + 4].push_back(idx + 2 * j + 2);
            graph[2 * y - 1].push_back(idx + 2 * j + 2);
        }
        idx += 2 * group[i].size();
    }

    for (int i = 0; i < b; i++) {
        int x, y;
        cin >> x >> y;
        graph[2 * x].push_back(2 * y - 1);
        graph[2 * y].push_back(2 * x - 1);
    }

	idx = 1;
	scc_num = 1;

	for (int i = 1; i < k; i++) {
		if (not visit[i]) {
			dfs(i);
		}
	}

	bool flag = true;
	for (int i = 1; i < 2 * n; i += 2) {
		if (scc_idx[i] == scc_idx[i + 1]) {
			cout << "NIE";
			flag = false;
			break;
		}
	}
	if (flag) cout << "TAK";
}