2-SAT,用连通分量编号确定答案
并非拓扑序,从树来看,若a比a非深度更深切a非为a的祖先节点,则必不能选a非,只能选a,如果a非不为a的祖先
#include<bits/stdc++.h>
//#define int long long
#define pll pair<int,int>
using namespace std;
const int N = (1e6+10)*2;
vector<int>e[N];
int dfncnt = 0, dfn[N], low[N], sc, scc[N], in_stack[N], tp, s[N];
int in[N];
void tarjan(int u) {dfn[u] = low[u] = ++dfncnt;s[++tp] = u; in_stack[u] = 1;for (auto& v : e[u]) {if (!dfn[v]) {tarjan(v);low[u] = min(low[u], low[v]);}else if (in_stack[v])low[u] = min(low[u], dfn[v]);}if (low[u] == dfn[u]) {int v; sc++;do {v = s[tp--];scc[v] = sc;in_stack[v] = 0;} while (v != u);}
}
signed main() {ios::sync_with_stdio(0);cin.tie(0);int n, m;cin >> n >> m;while (m--) {int i, a, j, b;cin >> a >> i >> b >> j;e[a * 2 + !i].push_back(b * 2 + j);e[b * 2 + !j].push_back(a * 2 + i);}for (int i = 1; i <= 2 * n + 2; i++) {if (!dfn[i])tarjan(i);}for (int i = 1; i <= n; i++) {if (scc[i * 2] != scc[i * 2 + 1])continue;cout << "IMPOSSIBLE\n";return 0;}cout << "POSSIBLE\n";for (int i = 1; i <= n; i++)cout<<(scc[i * 2] > scc[i * 2 + 1])<<' ';cout << '\n';return 0;
}
节点,则选哪个都不冲突