Tarjan/2-SAT学习笔记

时间: 2020-11-25｜32次围观｜0 条评论

Tarjan/2-SAT

Tags：图论

作业部落

评论地址

Tarjan

用来求割边或者割点，求点双联通分量或者边双联通分量
点双联通分量：两个点之间有两条点不相交的路径
边双联通分量：两个点之间有两条边不相交的路径
Tarjan求LCA还不会

2-SAT

每种物品有选或者不选两种状态，有些限制条件形如
选了\(A\)则必须选\(B\)，\(A\)和\(B\)不能同时选，必须选\(A\)等等
把逻辑限制关系变成连边
a->b表示如果\(a\)成立那么\(b\)一定成立
这个要求你理解逆否命题
逆否命题，举个例子，选\(A\)必须选\(B\)，那么我选了\(B'\)就不能选\(A\)，选\(B'\)就必须选\(A'\)
由于逆否命题产生的对称性使得\(2-SAT\)问题得以在\(O(n)\)时间求解
具体来说要求同时连接x->y y'->x'
这样跑一遍\(Tarjan\)缩点后如果统一物品的两种状态在同一个边双连通分量中就无解
否则可以输出方案，具体来说是每个点选择\(Tarjan\)缩成的超级点中编号最小的那个（也就是反图拓扑序最小的那个）

题单

Tarjan

2-SAT

Code

边双

void Tarjan(int x) { vis[x]=1;sta[++top]=x; dfn[x]=low[x]=++tot; for(int i=A.head[x],R=A.a[i].to;i;i=A.a[i].next,R=A.a[i].to) if(!dfn[R]) Tarjan(R),low[x]=min(low[x],low[R]); else if(vis[R]) low[x]=min(low[x],low[R]); if(low[x]!=dfn[x]) return; for(int k=sta[top],lst=0;lst!=x;lst=k,k=sta[--top]) vis[k]=0,bel[k]=x,val[x]+=val[k]*(k!=x); }

点双

void Tarjan(int x,int f) { int s=0;dfn[x]=low[x]=++tot; for(int i=head[x];i;i=a[i].next) { int R=a[i].to;if(R==f) continue; if(dfn[R]) {low[x]=min(low[x],dfn[R]);continue;} s++;Tarjan(R,x);tag[x]|=low[R]>=dfn[x]; low[x]=min(low[x],low[R]); } if(!f&&s==1) tag[x]=0; }

！注意点双第7行一定要是dfn[R]

2-sat（和平委员会）

#include<cstdio> #include<cstdlib> #include<queue> using namespace std; const int N=41000; struct edge {int next,fr,to;}; struct Map { edge a[N]; int head[N],cnt; void link(int x,int y) {a[++cnt]=(edge){head[x],x,y};head[x]=cnt;} }A,B; int dfn[N],top,sta[N],vis[N],low[N]; int bel[N],tot,n,m,p[N],node; queue<int> Q; void Min(int &a,int b) {if(b<a) a=b;} void Tarjan(int x) { vis[x]=1;sta[++top]=x; dfn[x]=low[x]=++tot; for(int i=A.head[x],R=A.a[i].to;i;i=A.a[i].next,R=A.a[i].to) if(!dfn[R]) Tarjan(R),Min(low[x],low[R]); else if(vis[R]) Min(low[x],low[R]); if(low[x]!=dfn[x]) return;++node; for(int k=sta[top],lst=0;lst!=x;lst=k,k=sta[--top]) vis[k]=0,bel[k]=node; } int main() { // freopen("spo.in","r",stdin); // freopen("spo.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=n*2;i++) p[i]=i&1?i+1:i-1; for(int i=1;i<=m;i++) { int x,y;scanf("%d%d",&x,&y); A.link(x,p[y]);A.link(y,p[x]); } for(int i=1;i<=n*2;i++) if(!dfn[i]) Tarjan(i); for(int i=1;i<=n*2;i+=2) if(bel[i]==bel[p[i]]) {puts("NIE");exit(0);} for(int i=1;i<=n*2;i+=2) printf("%d\n",bel[i]<bel[p[i]]?i:p[i]); }

转载于:https://www.cnblogs.com/xzyxzy/p/9457166.html

原文链接：https://blog.csdn.net/weixin_30342827/article/details/95860467

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。

本博客所有文章如无特别注明均为原创。
复制或转载请以超链接形式注明转自起风了，原文地址《Tarjan/2-SAT学习笔记》
　 　

还没有人抢沙发呢~