【範例】2-SAT(例1)
【題目敘述】https://cses.fi/problemset/task/1684/
【解題想法 】SCC + 拓撲排序 + 2-SAT
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
int n, m, a, b, dfn[200005], stk[200005], low[200005], pa[200005], opp[200005], in[200005], pick[200005], scc, idx;
char c[2];
vector <int> v[200005];
vector <int> v2[200005];
stack <int> st;
void tarjan(int x){
idx++;
dfn[x] = low[x] = idx;
st.push(x);
stk[x] = 1;
for (auto i:v[x]){
if (!dfn[i]){
tarjan(i);
low[x] = min(low[x], low[i]);
}
else if (stk[i]){
low[x] = min(low[x], dfn[i]);
}
}
if (dfn[x] == low[x]){
scc++;
pa[x] = scc;
int nxt = -1;
while (nxt != x){
nxt = st.top();
st.pop();
pa[nxt] = scc;
stk[nxt] = 0;
}
}
}
int tr(int x){
if (x <= m) return x+m;
else return x-m;
}
bool check(){
for (int i = 1; i <= m; i++){
if (pa[i] == pa[i+m]) return 0;
else{
opp[pa[i]] = pa[i+m];
opp[pa[i+m]] = pa[i];
}
}
return 1;
}
void build(){
for (int i = 1; i <= m * 2; i++){
for (int j:v[i]){
if (pa[i] != pa[j]){
v2[pa[j]].push_back(pa[i]);
in[pa[i]]++;
}
}
}
}
void topo(){
queue <int> q;
for (int i = 1; i <= scc; i++){
if (in[i] == 0) q.push(i);
}
while (!q.empty()){
int now = q.front();
q.pop();
if (!pick[now]){
pick[now] = 1;
pick[opp[now]] = 2;
}
for (auto i:v2[now]){
in[i]--;
if (!in[i]) q.push(i);
}
}
for (int i = 1; i <= m; i++){
if (pick[pa[i]] == 1) cout << "+ ";
else cout << "- ";
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++){
cin >> c[0] >> a >> c[1] >> b;
if (c[0] == '-') a += m;
if (c[1] == '-') b += m;
v[tr(a)].push_back(b);
v[tr(b)].push_back(a);
}
for (int i = 1; i <= m*2; i++){
if (!dfn[i]) tarjan(i);
}
if (check()){
build();
topo();
}
else cout << "IMPOSSIBLE\n";
}