[关闭]
@xzyxzy 2018-08-16T23:48:36.000000Z 字数 1918 阅读 508

Tarjan/2-SAT

图论

作业部落

评论地址


Tarjan

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

2-SAT

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

题单

Tarjan

2-SAT

Code

边双

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

点双

  1. void Tarjan(int x,int f)
  2. {
  3. int s=0;dfn[x]=low[x]=++tot;
  4. for(int i=head[x];i;i=a[i].next)
  5. {
  6. int R=a[i].to;if(R==f) continue;
  7. if(dfn[R]) {low[x]=min(low[x],dfn[R]);continue;}
  8. s++;Tarjan(R,x);tag[x]|=low[R]>=dfn[x];
  9. low[x]=min(low[x],low[R]);
  10. }
  11. if(!f&&s==1) tag[x]=0;
  12. }

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

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注