Holes To Fill

2-SAT

souvenir

一般就是每个变量为 \(0 / 1\)，给出很多个关于两个变量的约束然后求解啥的。下文设 \(x\) 表示 \(1\)，\(x'\) 表示 \(0\)。比如 \(x \oplus y = 1\)，则连边 \(x \to y'\)，\(x' \to y\)，\(y \to x'\)，\(y' \to x\)（单向的）。

faire

可以暴力 DFS。时间复杂度 \(\mathcal O(n ^ 2)\)。

bool dfs(int u) { // 这份代码 u ^ 1 为反集
	if (vis[u]) return true;
	if (vis[u ^ 1]) return false;
	vis[u] = true;
	s.push(u);
	for (const int &v : e[u])
		if (!dfs(v))
			return false;
	return true;
}


for (int i = 0; i < 2 * n; i += 2)
	if (!vis[i] && !vis[i + 1]) {
		while (s.size()) s.pop();
		if (!dfs(i)) {
			while (s.size()) vis[s.top()] = false, s.pop();
			if (!dfs(i + 1)) return cout << "NIE" << endl, 0;
		}
	}
for (int i = 0; i < 2 * n; i += 2)
	if (vis[i + 1]) cout << i + 2 << endl;
	else cout << i + 1 << endl; // 这个是当时编号，输出加了 1

也可以用 Tarjan 强连通分量缩点，根据所在强连通分量编号确定。时间复杂度 \(\mathcal O(n + m)\)。

void dfs(int u, int fa) {
	dfn[u] = low[u] = ++cnt;
	s.push(u);
	for (const int &v : e[u]) {
		// if (v == fa) continue;
		if (!dfn[v]) {
			dfs(v, u);
			low[u] = min(low[u], low[v]);
		}
		else if (!scc_id[v]) low[u] = min(low[u], dfn[v]);
	}
	if (low[u] == dfn[u]) {
		int t;
		scc_cnt++;
		do {
			t = s.top(); s.pop();
			scc_id[t] = scc_cnt;
		} while (t != u);
	}
}

for (int i = 1; i <= 2 * n; i++)
	if (!dfn[i]) dfs(i, i);
for (int i = 1; i <= n; i++)
	if (scc_id[i] == scc_id[i + n])
		return cout << "IMPOSSIBLE" << endl, 0;
cout << "POSSIBLE" << endl;
for (int i = 1; i <= n; i++)
	cout << (scc_id[i] > scc_id[i + n]) << " ";

quelque chose

如果要确定字典序最小啥的，只能上 DFS。

关于 DFS 解的构造，看代码 \(vis\) 数组显然；关于 Tarjan 解的构造，如果 \(x\) 和 \(x'\) 在同一 SCC 中无解，否则设 \(scc\_id_i\) 表示 \(i\) 的 SCC 编号，选更小的就好。也就是说，如果 \(scc\_id_x < scc\_id_{x'}\) 就选 \(x\)，否则选 \(x'\)。证明见 解的构造。

如果强制 \(x\) 为 \(0\)，可以连边 \(x \to x'\)，vice versa。感性理解就是”即使你选了 \(1\)，也给我走另一条路到 \(0\)“。

一道题目中，不同的 \(x\) 和 \(x'\) 含义可能不同，但是只要每个 \(x\) 只有 \(x\) 和 \(x'\) 就能 2-SAT。如 游戏。

Tarjan 相关

souvenir

主要是割点、割边（桥）、点双连通分量、边双连通分量、强连通分量。