Tarjan/2-SAT

图论

作业部落

评论地址

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

• [luogu3387]【模板】缩点 https://www.luogu.org/problemnew/show/P3387
• [luogu3388]【模板】割点（割顶）https://www.luogu.org/problemnew/show/P3388
• [APIO2009]抢掠计划 https://www.luogu.org/problemnew/show/P3627
• [HAOI2006]受欢迎的牛 https://www.luogu.org/problemnew/show/P2341
• [USACO5.3]校园网 https://www.luogu.org/problemnew/show/P2746
• [luogu3398]仓鼠找sugar https://www.luogu.org/problemnew/show/P3398
• [HNOI2006]潘多拉的宝盒 https://www.luogu.org/problemnew/show/P2321
• [HAOI2010]软件安装 https://www.luogu.org/problemnew/show/P2515
• [HNOI2012]矿场搭建 https://www.luogu.org/problemnew/show/P3225
• [SDOI2010]所驼门王的宝藏 https://www.luogu.org/problemnew/show/P2403

2-SAT

• [POI2001]和平委员会 http://cogs.pro:8080/cogs/problem/problem.php?pid=313
• [JSOI2010]满汉全席 https://www.luogu.org/problemnew/show/P4171
• [UOJ210]寻找罪犯 http://uoj.ac/problem/210
• [NOI2017]游戏 https://www.luogu.org/problemnew/show/P3825
• [HNOI2010]平面图判定 https://www.luogu.org/problemnew/show/P3209
• [POI2010]KOL-Railway https://www.luogu.org/problemnew/show/P3497

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]