牛客寒假算法训练营2处女座与宝藏（2-sat）
为了补这道题专门花了一下午学了2-sat
理论倒是好懂，就是建模方法想了很久，发现一篇很好的博文，直接贴过来好了。
----------------------------------------------------------------------------------------------------
模型一：两者（A，B）不能同时取
那么选择了A就只能选择B’，选择了B就只能选择A’
连边A→B’，B→A’
模型二：两者（A，B）不能同时不取
那么选择了A’就只能选择B，选择了B’就只能选择A
连边A’→B，B’→A
模型三：两者（A，B）要么都取，要么都不取
那么选择了A，就只能选择B，选择了B就只能选择A，选择了A’就只能选择B’，选择了B’就只能选择A’
连边A→B，B→A，A’→B’，B’→A’
模型四：两者（A，A’）必取A
那么，那么，该怎么说呢？先说连边吧。
连边A’→A
你想出来为什么了吗？也许你在想，哇塞，这样就保证了在反图中A在拓扑序中靠前，然后就会先选择A，呵呵，你错了。
虽然，我在一些人的博客中见到了这样的解释，但是，我还是非常负责任的告诉你，这是不全面的。
我们从A’向A连边，要的不仅是拓扑序，还有判可行与否。在2-sat图当中，若该图是可行的，就意味着如果从A到A’有路径的话，A’到A是没有路径的，因为如果有路径，它们就成一个块了，不会被判为可行，那么，如果A到A’是有路径的话，在反图中，A’就到A有路径，那么拓扑里，A’就会因为靠前被标记为“选择”，并未满足条件。并且，我们应当确信的是，解的多情况依赖的是拓扑排序的多情况，不按拓扑序来的话，解就是错误的，或者说是不成立的，也就是说，我们拓扑序先选择A的话，就会导致别的约束条件的不成立，那么在我们引入了A’到A的这条边后，A就与A’在同一块中了，算法会报告不可行信息。若是原图本来就满足A到A’有路径，然而A’到A无路径的话，我们添一条边，只是确定了其有解，但丝毫不会影响到拓扑排序，只有当A到A’之间根本不存在路径的时候，才会影响到其拓扑排序，所以，真相是这样的。
是不是有人已经开始疑惑，讲了这么久的对称性，整个算法都是依赖对称性才得以成立的，那么怎么一下引入一条边让图不对称了算法还成立呢！关于这个问题，其实很好解释，仔细想想，对称性确保的是什么？它确保的可是原图有解，则一定可以构造出来。现在我们引入了一条边A’→A，若通过上述判断，让其无解了，那么对后面显然是没有影响的，毕竟算法都没执行下去了，还算什么影响。如果还有解呢？这说明了什么？这说明了A’到A原本就存在一条路径，或者A’到A之间根本就没有路径。如果有路径的话，那么我多增加一条有区别吗？它会影响到算法的任何一步吗？显然不会啊，那如果原本没有路径的话呢？没有路径意味着谁在拓扑序列中靠前都是可能的，在有了该边后（反边为A→A’），A将在拓扑序列中靠前，被标记为“选择”，那么我们会对A’进行直接标记，此时，A’到A是没有路可走的，它根本就无法访问到A，所以在标记的这个过程中，这条路径根本就没有影响到图的任何对称性，在拓扑排序后，你完全可以当其不存在。
----------------------------------------------------------------------------------------------------
关于求强连通分量的办法
刚开始学的是kosaraju算法（Two-Phase DFS），其实是因为tarjan没看懂，然后退而求其次学的这个，等到把这个学会以后再反过来看tarjan，才发现tarjan和这个的思想一模一样，只不过是tarjan巧妙的利用了栈的特性，从而不必dfs两次，虽然两者复杂度一样，但tarjan显然更快。
这里的low[u]定义为该dfs遍历对应的dfs树中，以点u为根的子树上的 所有点能够通过某一条非树边连向的点中dfn的最小值，其中dfn记录的是点的dfs序。
理解了low数组的定义以后，tarjan算法的核心思想不过就是把所有low[x]=dfn[x]的点作为一个根节点，它的dfs子节点和它就组成了一个强连通块。按照kosaraju算法的描述，其实是需要先dfs一次产生逆dfs序的，但tarjan利用dfs深度优先的特性以及栈的存储特性，在回溯的过程中巧妙的实现了逆dfs序进行强联通块的构建。笔者代码中的cnt记录了强连通块的编号，容易发现，它从大到小恰好就是一个缩完点之后新图的拓扑序。
代码如下
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
vector<int> v[maxn];
vector<int> g[2*maxn];
int a[maxn];
int dfn[2*maxn];
int low[2*maxn];
int belong[2*maxn];
bool instack[2*maxn];
int st[2*maxn];
int num[2*maxn];
int top=0;
int id=0;
int cnt=0;
int n,m;
void tarjan(int x)
{
dfn[x]=low[x]=++id;
instack[x]=true;
st[++top]=x;
for(int i=0;i<g[x].size();i++)
{
int now=g[x][i];
if(!dfn[now])
{
tarjan(now);
low[x]=min(low[x],low[now]);
}
else if(instack[now]&&low[x]>dfn[now])
low[x]=dfn[now];
}
if(low[x]==dfn[x])
{
cnt++;
int now;
do
{
now=st[top--];
instack[now]=0;
belong[now]=cnt;
num[now]++;
}while(x!=now);
}
}
bool solve()
{
for(int i=1;i<=2*m;i++)
{
if(!dfn[i])
tarjan(i);
}
for(int i=1;i<=2*m;i+=2)
{
if(belong[i]==belong[i^1])
return false;
}
return true;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=m;i++)
{
int k;
cin>>k;
int x;
for(int j=1;j<=k;j++)
{
cin>>x;
v[x].push_back(i);
}
}
int flag=1;
for(int i=1;i<=n;i++)
{
if(v[i].size()==2)
{
int x=v[i][0]<<1;
int y=v[i][1]<<1;
if(a[i]==1)
{
g[x].push_back(y^1);
g[x^1].push_back(y);
g[y^1].push_back(x);
g[y].push_back(x^1);
}
else
{
g[x].push_back(y);
g[x^1].push_back(y^1);
g[y^1].push_back(x^1);
g[y].push_back(x);
}
}
else if(v[i].size()==1)
{
int x=v[i][0]<<1;
if(a[i]==1)
g[x^1].push_back(x);
else g[x].push_back(x^1);
}
else if(v[i].size()==0)
{
if(a[i]==1)
{
flag=0;
break;
}
}
}
if(flag&&solve())
cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return 0;
}