https://www.acmicpc.net/problem/7535
7535번: A Bug’s Life
The output for every scenario is a line containing “Scenario #i:”, where i is the number of the scenario starting at 1, followed by one line saying either “No suspicious bugs found!” if the experiment is consistent with his assumption about the bugs’ sexua
www.acmicpc.net
각 항이 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";
}
}
'알고리즘 > 백준 & swacademy' 카테고리의 다른 글
BOJ 11444 - 피보나치 수 6 (행렬곱, 점화식 이용) (0) | 2019.09.27 |
---|---|
BOJ 2749 - 피보나치 3 (MOD=10^k꼴일 때 주기 이용) (0) | 2019.09.27 |
BOJ 4013 - ATM (0) | 2019.08.19 |
BOJ 1005 - ACM 크래프트 (위상정렬) (0) | 2019.08.19 |
BOJ 2887 - 행성터널 (0) | 2019.08.19 |