Tarjan学习笔记
小菜鸟
2019-05-27 15:29:56
很久之前就想学$Tarjan$了，然而由于各种奇怪的原因直到上过课才学会。
于是来写一篇学习笔记$\&$题解。。。
$Tarjan$是$Robert\;Tarjan$发明的一种基于$DFS$的求解强连通分量及割点等图论问题的算法，复杂度$O(n+m)$，十分高效。
$Tarjan$使用一个栈来维护当前搜过的路径信息，并使用$DFS$序时间戳来判断是否找到了环。
用$dfn_i$表示点$i$的$DFS$序，$low_i$表示从点$i$出发能到达的点中最小的$DFS$序，每次遇到已入栈的点就不断退栈染色即可。。。
代码实现不算麻烦：
```cpp
int cnt;
int col;
void tarjan(int u)
{
static stack<int> st;
low[u]=dfn[u]=++cnt;
vis[u]=1;
st.push(u);
for(int i=head[u];i;i=E[i].next)
{
int v=E[i].to;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else
{
if(vis[v])
{
low[u]=min(low[u],dfn[v]);
}
}
}
if(dfn[u]==low[u])
{
int t=-1;
++col;
while(t!=u)
{
t=st.top();
st.pop();
color[t]=col;
vis[t]=0;
}
}
}
```
如果要把求出的强联通分量缩点：
```cpp
void shrink_point()
{
for(int i=1;i<=n;++i)
{
if(!dfn[i])tarjan(i);
}
for(int u=1;u<=n;++u)
{
for(int i=head[u];i;i=E[i].next)
{
int v=E[i].to;
if(color[u]!=color[v])
{
_add(color[u],color[v]);
}
}
}
}
```
求解$2\_SAT$问题：
```cpp
bool two_SAT()
{
for(int i=1;i<=n<<1;++i)
{
if(!dfn[i])tarjan(i);
}
for(int i=1;i<=n;++i)
{
if(color[i]==color[i+n])return 0;
}
return 1;
}
```
然后变量$a_i$取$true$对应$[1,n]$的点编号，取$false$对应$[n+1,2n]$的点编号。
然后$a_i$的取值就是$color[i]>color[i+n]$。
求解割点：
```cpp
void tarjan(int u,int rt)
{
int rec=0;
static int cnt=0;
static stack<int> st;
low[u]=dfn[u]=++cnt;
vis[u]=1;
st.push(u);
for(int i=head[u];i;i=E[i].next)
{
int v=E[i].to;
if(!dfn[v])
{
tarjan(v,rt);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]&&u!=rt)
{
cut[u]=1;
}
if(u==rt)
{
++rec;
}
}
low[u]=min(low[u],dfn[v]);
}
if(u==rt&&rec>1)cut[rt]=1;
}
```