本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-11-04 19:31:40

题目链接

我们要判断一个变量恒为真/假/真假都可以。

方法一

我们可以强行设 $x_i$ 为假，若无解，那么 $x_i$ 一定为真或真假都行，或都不行。

要跑 $n$ 次，所以时间复杂度是 $O(nm)$。

方法二

若 $x_i$ 是指向 $\neg x_i$ 的话，我们就一定选 $x_i$ 为假。

若 $\neg x_i$ 是指向 $x_i$ 的话，我们就一定选 $\neg x_i$ 为假。

否则若 $\neg x_i$ 和 $x_i$ 没有可达关系，那么就是 ?。

那么这样的话，我们就可以判断两个点是否有可达关系就可以了，而判断可达关系的话就可以用 BFS 或 DFS。

时间复杂度为 $O(n^2)$。

CODE:

#include <bits\/stdc++.h>
using namespace std;
const int N = 2010;
int n, m;
bool ins[N], vis[N];
vector<int> e[N];
int dfn[N], low[N], idx, bel[N];
stack<int> stk;
int cnt;
char ans[N];
void taryan(int u) {\/\/联通分量
	dfn[u] = low[u] = ++idx;
	ins[u] = true;
	stk.push(u);
	for (auto v: e[u]) {
		if (!dfn[v]) taryan(v);
		if (ins[v]) low[u] = min(low[u], low[v]);
	}
	if (dfn[u] == low[u]) {
		++cnt;
		while (true) {
			int v = stk.top();
			bel[v] = cnt;
			ins[v] = false;
			stk.pop();
			if (u == v) break;
		}
	}
}
void dfs2(int u) {\/\/dfs
	vis[u] = 1;
    for (auto v : e[u]) if (!vis[v])
        dfs2(v);
}
bool check(int s, int t) {
    memset(vis, false, sizeof(vis));
    dfs2(s);
    return vis[t];
}
int main() {
	scanf("%d%d", &n, &m);
    	for (int i = 1; i <= m; ++i) {
		int u, v;
		char ty1[2], ty2[2];
		scanf("%d%s%d%s", &u, ty1, &v, ty2);
		--u, --v;
		u = (u * 2) + (*ty1 == 'Y');
		v = (v * 2) + (*ty2 == 'Y');
		e[u ^ 1].push_back(v);
		e[v ^ 1].push_back(u);
	}
	for (int i = 0; i < 2 * n; ++i) if (!dfn[i])
		taryan(i);
	for (int i = 0; i < n; ++i) {
		if (bel[i << 1] == bel[i << 1 | 1]) {
			puts("IMPOSSIBLE");\/\/无解
			return 0;
		}
	}
    for (int i = 0; i < n; ++i) {
        if (check(2 * i, 2 * i + 1)) ans[i] = 'Y';\/\/当i*2是2*i+1,则第i个恒为真
        else if (check(2 * i + 1, 2 * i)) ans[i] = 'N';\/\/另一种情况
        else ans[i] = '?';\/\/因为不会是无解，所以就是?
    }
    puts(ans);
    return 0;
}