BOJ 7535 - A Bug's Life

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

7535번: A Bug’s Life

 

각 항이 xor로 묶여있는 2-Sat문제이다.

 

p번 벌레가 q번 벌레와 소통했을 때 둘의 성별이 달라야 한다. 이를 p xor q로 나타낼 수 있다.

 p xor q === (notp -> q && notq->p) && (p->notq && q->notp)

https://suuntree.tistory.com/43 참고

 

 

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#include <string>
#define MAX 2001
using namespace std;

int id, dfsn[MAX * 2], SN, sn[MAX * 2];
bool finished[MAX * 2];
vector<int> adj[MAX * 2];
stack<int> s;
string answer[2]{ "","No " };

void initGlobal() {
	id = SN = 0;
	fill(dfsn, dfsn + MAX * 2, 0);
	fill(sn, sn + MAX * 2, 0);
	fill(finished, finished + MAX * 2, 0);
	for (int i = 0; i < MAX * 2; i++)
		adj[i].clear();
}

int NOT(int p) {
	return p % 2 ? p - 1 : p + 1;
}

int makeSCC(int curr) {
	dfsn[curr] = ++id;
	s.push(curr);

	int parent = dfsn[curr];
	for (int next : adj[curr]) {
		if (dfsn[next] == 0) parent = min(parent, makeSCC(next));
		else if (!finished[next]) parent = min(parent, dfsn[next]);
	}
	if (parent == dfsn[curr]) {
		while (1) {
			int t = s.top(); s.pop();
			finished[t] = true;
			sn[t] = SN;
			if (t == curr) break;
		}
		SN++;
	}
	return parent;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int testcase; cin >> testcase;
	for (int tc = 1; tc <= testcase; tc++) {
		initGlobal();
		int n, m; cin >> n >> m;
		for (int i = 0, u, v; i < m; i++) {
			cin >> u >> v;
			u = u * 2 - 1;
			v = v * 2 - 1;
			adj[NOT(u)].push_back(v);
			adj[NOT(v)].push_back(u);
			adj[u].push_back(NOT(v));
			adj[v].push_back(NOT(u));
		}
		for (int i = 0; i < 2 * n; i++)
			if (dfsn[i] == 0) makeSCC(i);

		bool flag = true;
		for (int i = 0; i < n; i++)
			if (sn[i * 2] == sn[i * 2 + 1]) flag = false;

		cout << "Scenario #" << tc << ":\n";
		if (flag)
			cout << "No suspicious bugs found!\n\n";
		else
			cout << "Suspicious bugs found!\n\n";
	}
}