前后缀和优化建图

先把遇到的问题放出来，然后再解决问题。

题目链接：Riddle

很明显，这是一道$2-SAT$问题，每条边至少有一个端点是关键点，若我们用$x$表示$x$是关键点，$x+n$表示$x$不是关键点，则对于一条边$x-y$，我们可以得到$x+n->y,y+n->x$。而每个部分$S$恰好有一个关键点，那么我们可以表示为$x->y+n\quad (x,y\in S \wedge y\ne x)$，建好图后跑一遍$Tarjan$就好了。但是直接建图的话时间复杂度会爆炸，这个时候我们就要考虑优化建图了。我们发现，在一个集合中，每个点向除了自己外的所有点连边就相当于向某个前缀连边和向某个后缀连边，因此我们可以用前后缀和的思想优化，我画出来图你们就应该都明白了。

然后就灰常的$easy$了。

#include<bits/stdc++.h>
#define x first
#define y second
#define endl '\n'
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define lowbit(x) ((x)&-(x))
#define SZ(x) (int)x.size()
using namespace std;
using ll=long long;
using ld=long double;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using pdd=pair<ld,ld>;
const int N=4e6+10,M=8e6+10;
int n,m,k;
int e[M],ne[M],h[N],idx=1;
int tmp[N];
void add(int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int cnt,s[N],timestamp,id[N],stk[N],top,dfn[N],low[N];
bool st[N];
void tarjan(int u){
	dfn[u]=low[u]=++timestamp;
	stk[++top]=u,st[u]=1;
	for(int i=h[u];i;i=ne[i]){
		int j=e[i];
		if(!dfn[j]){
			tarjan(j);
			low[u]=min(low[j],low[u]);
		}
		else if(st[j]) low[u]=min(low[u],dfn[j]);
	}
	if(dfn[u]==low[u]){
		int tmp;
		cnt++;
		do{
			tmp=stk[top--];
			st[tmp]=0;
			id[tmp]=cnt;
			s[cnt]++;
		}while(tmp!=u);
	}
}
void solve(){
	cin>>n>>m>>k;
	while(m--){
		int a,b;
		cin>>a>>b;
		add(a+n,b);
		add(b+n,a);
	}
	for(int i=1;i<=k;i++){
		int num;
		cin>>num;
		for(int j=1;j<=num;j++){
			cin>>tmp[j];
			add(tmp[j]+2*n,tmp[j]+n);//前缀
			add(tmp[j]+3*n,tmp[j]+n);//后缀
		}
		for(int j=1;j<num;j++){
			add(tmp[j+1]+2*n,tmp[j]+2*n);
			add(tmp[j]+3*n,tmp[j+1]+3*n);
		}
		for(int j=1;j<=num;j++){
			if(j!=1){
				add(tmp[j],tmp[j-1]+2*n);
			}
			if(j!=num){
				add(tmp[j],tmp[j+1]+3*n);
			}
		}
	}
	for(int i=1;i<=2*n;i++)
		if(!dfn[i])
			tarjan(i);
	for(int i=1;i<=n;i++)
		if(id[i]==id[i+n])
			return cout<<"NIE"<<endl,void();
	cout<<"TAK"<<endl;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	solve();
	return 0;
}