luoguP4782 [模板]2-SAT问题

https://www.luogu.org/problemnew/show/P4782

2-SAT模板，输出方案只需判断 \(a\) 和 \(a + n\) 两个点所在的 scc 编号大小就可以了

#include <bits/stdc++.h>

using namespace std;

template <typename T>

inline void read(T &f) {

	f = 0; T fu = 1; char c = getchar();

	while (c < '0' || c > '9') {if (c == '-') fu = -1; c = getchar();}

	while (c >= '0' && c <= '9') {f = (f << 3) + (f << 1) + (c & 15); c = getchar();}

	f *= fu;

}

const int N = 2000000 + 10;

struct Edge {

	int u, v, next;

}G[N << 1];

int head[N], col[N], low[N], dfn[N], st[N], inst[N];

int n, m, tot, cnt, Index, len;

inline void addedge(int u, int v) {

	G[++tot] = (Edge) {u, v, head[u]}, head[u] = tot;

}

void tarjan(int u) {

	low[u] = dfn[u] = ++Index;

	st[++len] = u; inst[u] = 1;

	for(int i = head[u]; i; i = G[i].next) {

		int v = G[i].v;

		if(!dfn[v]) {

			tarjan(v);

			low[u] = min(low[u], low[v]);

		} else if(inst[v]) low[u] = min(low[u], dfn[v]);

	}

	if(low[u] == dfn[u]) {

		cnt++;

		while(st[len + 1] != u) {

			int tmp = st[len--];

			col[tmp] = cnt;

			inst[tmp] = 0;

		}

	}

} 

int main() {

	read(n); read(m);

	for(int i = 1; i <= m; i++) {

		int a, b, c, d;

		read(a); read(b); read(c); read(d);

		if(b == 0) {

			if(d == 0) addedge(a + n, c), addedge(c + n, a);

			else addedge(a + n, c + n), addedge(c, a);

		} else {

			if(d == 0) addedge(a, c), addedge(c + n, a + n);

			else addedge(a, c + n), addedge(c, a + n);

		}

	}

	for(int i = 1; i <= (n << 1); i++) if(!dfn[i]) tarjan(i);

	for(int i = 1; i <= n; i++) if(col[i] == col[i + n]) {puts("IMPOSSIBLE"); return 0;}

	puts("POSSIBLE");

	for(int i = 1; i <= n; i++) if(col[i] > col[i + n]) printf("1 "); else printf("0 ");

	return 0;

}

巴特西

luoguP4782 [模板]2-SAT问题

最新文章

热门文章