P6378[PA2010]Riddle【2SAT】

正题

题目链接:https://www.luogu.com.cn/problem/P6378

---

题目大意

给出\(n\)个点\(m\)条边的一张无向图，图中有\(k\)种颜色的点。

要求每种颜色选择一个点作为关键点，满足每条边两边至少有一个关键点

求是否有满足的方案

\(1\leq n,m,k\leq 10^6\)

---

解题思路

如果想到\(2-SAT\)的话就挺好解决的了。

然后一个经典的问题是一堆点里面选了一个点就不能选其他点。

可以考虑优化建图，搞一些前缀点和一些后缀点就好了

时间复杂度\(O(n)\)

---

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
const int N=5e6+10;
struct node{
	int to,next;
}a[N<<1];
int n,m,k,cnt,tot,dfc,cfc;
int ls[N],dfn[N],low[N],col[N];
bool ins[N];vector<int> v[N];
stack<int> s;
void addl(int x,int y){
	a[++tot].to=y;
	a[tot].next=ls[x];
	ls[x]=tot;return;
}
void tarjan(int x){
	dfn[x]=low[x]=++dfc;
	s.push(x);ins[x]=1;
	for(int i=ls[x];i;i=a[i].next){
		int y=a[i].to;
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(ins[y])
			low[x]=min(low[x],dfn[y]);
	}
	if(low[x]==dfn[x]){
		++cfc;
		while(s.top()!=x){
			col[s.top()]=cfc;
			ins[s.top()]=0;
			s.pop();
		}
		col[s.top()]=cfc;
		ins[s.top()]=0;
		s.pop();
	}
	return;
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=m;i++){
		int x,y;scanf("%d%d",&x,&y);
		addl(x*2-1,y*2);addl(y*2-1,x*2);
	}
	cnt=2*n;
	for(int i=1;i<=k;i++){
		int w,x;scanf("%d",&w);
		v[i].push_back(0);
		for(int j=1;j<=w;j++){
			scanf("%d",&x);
			v[i].push_back(x);
		}
		cnt++;addl(cnt,v[i][1]*2-1);
		for(int j=2;j<=w;j++){
			addl(v[i][j]*2,cnt);
			++cnt;addl(cnt,cnt-1);
			addl(cnt,v[i][j]*2-1);
		}
		cnt++;addl(cnt,v[i][w]*2-1);
		for(int j=w-1;j>=1;j--){
			addl(v[i][j]*2,cnt);
			++cnt;addl(cnt,cnt-1);
			addl(cnt,v[i][j]*2-1);
		}
	}
	for(int i=1;i<=cnt;i++)
		if(!dfn[i])tarjan(i);
	for(int i=1;i<=n;i++)
		if(col[2*i]==col[2*i-1])return puts("NIE")&0;
	puts("TAK");return 0;
}