知识点：2-SAT，优化建图
Link：https://www.luogu.com.cn/problem/P6378。
2-SAT 前后缀优化建图套路。
对 2-SAT 本质的理解。
简述
给定一 \(n\) 个节点 \(m\) 条边的无向图，该无向图的所有节点被分为了 \(k\) 个部分。
要求选择一些关键点，使得每部分中恰有一个点是关键点，且每条边至少有一个端点是关键点。
仅需判断是否存在合法的选择方案。
\(1\le k\le n\le 10^6\)，\(0\le m\le 10^6\)。
3S，500MB。
分析
省流版：在 2-SAT 的建图中，代表 \(x=0\) 和 \(x=1\) 的节点才有实际意义，我们仅需关注它们之间联通情况即可。在此基础上新建其他节点都是为了使得它们更好地联通。
发现要求满足以下限制：
- 对于一条边上的两个节点，如果某端点不是关键点，那么另一个端点一定是关键点。
- 对于某个部分中的所有节点，如果其中某个节点为关键点，则其他所有点均不是能关键点。
显然的 2-SAT 问题。令节点 \(i\) 表示命题“不选择无向图中节点 \(i\) 为关键点”，节点 \(i+n\) 表示命题“选择无向图中节点 \(i\) 为关键点”。则限制一很好解决，对于原图中无向边 \((u, v)\)，在 2-SAT 中连有向边 \(<u, v + n>\) 与 \(<v, u + n>\) 即可。但是对于限制二，如果直接在点集内从某个点向其他点暴力连边，将最多有 \(O(n^2)\) 级别的边，无法通过本题。
考虑优化建图。对于点集 \(\{1, 2, \cdots w\}\) 维护前缀点 \(\operatorname{pre}_{1}\sim \operatorname{pre}_{w}\) 和后缀点 \(\operatorname{suf}_{1}\sim \operatorname{suf}_{w}\)。对于前缀点 \(\operatorname{pre} _{i}\) 连接有向边 \(<\operatorname{pre}_i, i >\) 与 \(<\operatorname{pre}_i, \operatorname{pre}_{i - 1}>\)，同理对于后缀点连接有向边 \(<\operatorname{suf}_i, i >\) 与 \(<\operatorname{suf}_i, \operatorname{suf}_{i + 1}>\)。在此基础上，在点集内从 \(i+n\) 向 \(\{1, 2, \cdots, i - 1, i + 1, \cdots, w\}\) 连有向边等价于仅连有向边 \(<i+n, \operatorname{pre}_{i - 1}>\) 与 \(<i + n, \operatorname{suf}_{i + 1}>\)。
上述过程中新增了 \(2\times n\) 级别的节点数，但将限制二的连边数减少到了 \(6\times n\) 级别。则 2-SAT 系统中总节点数为 \(4\times n\) 级别，总边数变为 \(8\times n\) 级别，可以通过本题。
代码
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 4e6 + 10;
const int kM = kN << 2;
//=============================================================
int n, m, k, nodenum;
int edgenum, head[kN], v[kM], ne[kM];
int dfnnum, belnum, dfn[kN], low[kN], bel[kN];
std::stack <int> st;
std::vector <int> s;
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Add(int u_, int v_) {
v[++ edgenum] = v_;
ne[edgenum] = head[u_];
head[u_] = edgenum;
}
void Tarjan(int u_) {
dfn[u_] = low[u_] = ++ dfnnum;
st.push(u_);
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i];
if (!dfn[v_]) {
Tarjan(v_);
low[u_] = std::min(low[u_], low[v_]);
} else if (!bel[v_]) {
low[u_] = std::min(low[u_], dfn[v_]);
}
}
if (dfn[u_] == low[u_]) {
++ belnum;
for (int i = 0; i != u_; st.pop()) {
i = st.top();
bel[i] = belnum;
}
}
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
n = read(), m = read(), k = read();
for (int i = 1; i <= m; ++ i) {
int u_ = read(), v_ = read();
Add(u_, v_ + n), Add(v_, u_ + n);
}
nodenum = 2 * n;
for (int i = 1; i <= k; ++ i) {
int w = read();
s.clear();
for (int j = 0; j < w; ++ j) {
s.push_back(read());
Add(s[j] + 2 * n, s[j]), Add(s[j] + 3 * n, s[j]);
if (j != 0) Add(s[j] + 2 * n, s[j - 1] + 2 * n);
if (j != 0) Add(s[j - 1] + 3 * n, s[j] + 3 * n);
}
for (int j = 0; j < w; ++ j) {
if (j != 0) Add(s[j] + n, s[j - 1] + 2 * n);
if (j != w - 1) Add(s[j] + n, s[j + 1] + 3 * n);
}
}
for (int i = 1; i <= nodenum; ++ i) {
if (!dfn[i]) Tarjan(i);
if (i <= n && bel[i] == bel[i + n]) {
printf("NIE\n");
return 0;
}
}
printf("TAK\n");
return 0;
}