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

[x] [luogu3387]【模板】缩点 https://www.luogu.org/problemnew/show/P3387
[x] [luogu3388]【模板】割点（割顶）https://www.luogu.org/problemnew/show/P3388
[x] [APIO2009]抢掠计划 https://www.luogu.org/problemnew/show/P3627
[x] [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
[x] [HNOI2006]潘多拉的宝盒 https://www.luogu.org/problemnew/show/P2321
[ ] [HAOI2010]软件安装 https://www.luogu.org/problemnew/show/P2515
[x] [HNOI2012]矿场搭建 https://www.luogu.org/problemnew/show/P3225
[ ] [SDOI2010]所驼门王的宝藏 https://www.luogu.org/problemnew/show/P2403

2-SAT

[x] [POI2001]和平委员会 http://cogs.pro:8080/cogs/problem/problem.php?pid=313
[x] [JSOI2010]满汉全席 https://www.luogu.org/problemnew/show/P4171
[x] [UOJ210]寻找罪犯 http://uoj.ac/problem/210
[x] [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]

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]);

}

巴特西

Tarjan/2-SAT学习笔记

Tarjan/2-SAT

作业部落

评论地址

Tarjan

2-SAT

题单

Tarjan

2-SAT

Code

边双

点双

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

2-sat（和平委员会）

最新文章

热门文章