题解 P4782 【【模板】2-SAT 问题】

TopCarry · 2019-01-30 21:41:47 · 题解

果然没有Kosaraju的题解╮(╯_╰)╭。

  事实上tarjan解2-SAT会很不自然，因为它的拓扑序其实是倒过来的，而Kosaraju就不会有这个烦恼，正好没人打，我来水一发。

  考虑到这个优秀的冷门算法大多数人不用，所以简单介绍一下。

关于Kosaraju

1. 代码不容易错

2. 思维上更好理解，更加自然。

3. 和2-SAT问题的原理上更加共通

   先上一波代码：

   void add(int x,int y){
   e[++tot].to=y;e[tot].next=head[x];head[x]=tot;
   e[++tot].to=x;e[tot].next=HEAD[y];HEAD[y]=tot;
   }

   void dfs1(int u){
   int i;
   vis[u]=1;
   for(i=head[u];i;i=e[i].next)
       if(!vis[e[i].to])
           dfs1(e[i].to);
   turn[++cnt]=u;
   }
   void dfs2(int u){
   belong[u]=cnt;vis[u]=1;
   for(int i=HEAD[u];i;i=e[i].next)
       if(!vis[e[i].to])
           dfs2(e[i].to);
   }
   void kosaraju(){
   for(int i=1;i<=2*n;i++)
       if(!vis[i])dfs1(i);
   reset(vis);cnt=0;
   for(int i=2*n;i>=1;i--)
       if(!vis[turn[i]])
           cnt++,dfs2(turn[i]);
   }

   原理很简单：

4. 考虑无向图的缩点，对于每个强联通分量，只要从这个块任意一个点开始跑到没点可去就可以了。

5. 然而有向图不可以，设A，B为两个强联通分量，当A->B时，我们依然无脑跑，把跑到的缩一起，但是呢，如果我们从A中的点开始跑，就会把A和B缩一起，这是我们不希望的，所以我们考虑让他总会从B开始遍历。

6. 我们使用“逆后序”，即先遍历该点的出点，在把它丢进去，相当于是“每个点跑完的顺序”。

void dfs1(int u){
    int i;
    vis[u]=1;
    for(i=head[u];i;i=e[i].next)
        if(!vis[e[i].to])
            dfs1(e[i].to);
    turn[++cnt]=u;
}

这样做会有一个很棒的性质，模拟一波过程：

  (1).从A开始跑，遍历顺序为:A->B->把B丢进栈->回溯到A->把A丢进栈。

  (2).从B开始跑，遍历顺序为:跑完B->把B丢进栈->因为边的方向是A到B而到不了A，退出->发现vis[A]=0->跑A->把A丢进栈。

  我们发现不管怎么样，栈顶都是A。   4.但是这个A很让人难受，相当于我们找到了一种方法，使栈顶永远都是那个不应该跑的点，这和第二条中的期望不符合诶。

  5.于是我们建一个反图，对于A和B，他们依然都是强联通的(比如环反向了还是一个环)，但是A->B的边变成了B->A，而A在栈顶，这就很完美!现在我们像无向图一样无脑遍历一遍就OK了。

呼，总算是讲完了，那么开始正式讲一波2-SAT。

  分析一波逻辑：

  1.<A=1或者B=1> = (当A不选,B一定得选;当B不选，A一定得选)

  2.<A=0或者B=0> =(当A选，B一定不选;当B选,A一定不选)

  3.<A=0或者B=1> =(当A选，B一定选;当B不选，A一定不选)