Tarjan 1.02 　　[USACO06JAN]牛的舞会The Cow Prom

前几天想要写的子糊串咕咕了，姑且从图开始吧；

Tarjan

首先来购买一些数组：

　　dfn【i】 ：i点的dfs序  （即dfs搜到i点时已经过的点数）

　　low【i】：i点所在的子树dfs序最小的点（可以认为是极浅的一个点）

　　num ：dfs序计数（这是什么时候混进来的？）

可它们是空的~~~~；

但不妨开始我们的递归之旅；

看图（图是到处都可以找得到的）

看到那个1号点了吗，从他开始；

于是有了一小段伪代码

dfs（1）

｛

　　dfn【1】=low【1】=++num；||  初始化 默认自己为全子树的根（但人家本来就是啊啊啊）

　　stack【++top】=1；||  手动入栈

　　for（可以去的点v（2  ，4））

　　｛

　　　　dfs（v）；|| 下一个

　　　　|| 更新总是在回溯的时候

　　　　low【1】=min（low【2】，low【1】）；||  最浅的当然还是low【1】=1了

　　｝

　　top--  ||出栈
｝

如此简单，

如果只考虑一个点的图当然简单了；

还有子节点，还要输出强连通分量，何以敌？

那不就完惹QAQ。。。（此文何用。。。？）

于是有了其他点的一小段伪代码

dfs（cur）

｛
　　dfn【cur】=low【cur】=++num；

　　cur进入stack

　　for（能到的点 v ）

　　｛

　　　　if（！dfn【v】）|| 深搜未到

　　　　｛

　　　　　　dfs（v）；

　　　　　　low【cur】=min （low【cur】 ， low【v】 ）；

　　　　｝

　　　　if（dfn 【v】 &&  in-stack【v】） || 深搜到过 ， 还在栈中 ， ==》 在同一个连通分量中 ==》 需要确定更浅的  

　　　　｛

　　　　　　low 【cur】 = min （low 【cur】，dfn【v】）

　　　　｝

　　｝

　　if（dfn【cur】==low【cur】）|| 更新后未被更小点取代，必定为某分量的顶点

　　｛

　　　　　　while（cur！=stack。top）　　　　

　　　　　　　　printf   stack。top || 打印      《》      染色||  color【stack。top】=totcolor

　　　　　　　　top 出栈

　　　｝||　　totcolor++

　　cur出stack； || 

｝

就上面那张tarjan入门必看图 

我们模拟一下运行过程 （抖癌晚期就不献图了）

上一个表格

特别说明2*一个令蒟蒻我蒙很久的地方：

从5号点望向（因为不能到QAQ）1号点时

失散多年的父子相见了

根据上文伪代码

　　low【5】= min（low【5】，dfn【1】）= 1    ==》  5在一个以1为顶点的子树

　　low【5】！=dfn【5】    ==》    5 不出栈，回到2，

　　 low【2】= min（low【2】，low【5】）= 1    ==》  2发现跟着5跟着1混更能体现自身价值，于是进入一个以1为顶点的子树  

　　目前栈中 ： 1 2 5；

　　low【2】！=dfn【2】    ==》   2不出栈，回到1；

　　1 还可以到4

　　4 没走过  ==》 入栈

　　dfn【4】=low【4】=6；

　　看见5，还在栈中，不能去；

　　low【4】= min （low【4】，dfn【5】 ）=5；

　　low【4】！= dfn【4】   ==》4 不出栈，回到1；

　　dfn【1】==low【1】   （ <-> _ <->  !）

　　都出去吧；

　　于是栈空，于是强连通分量求完；

这就完了？不可能的；

图不联通怎么破；

for（int i=1；i<=n; ++i）

{

　　if ( ! dfn[i]  )  dfs (i );           ||  其实dfn  也可以 换作 low  ，要是不嫌弃开个bool数组记录也行的哟

}　　

————————

这里口胡一下为什么low i ==dfn  i 时出栈能保证极大

　　当其子树 dfn   < dfn i  时才可以使  low i ==dfn  i  ；不然就更新了；

　　子树dfs序当然会比根小了；

　　也有些时候他的儿子与他的父亲暗地里勾结了

　　此时则得到一个SCC，直接回溯不弹出，是防止有其他儿子勾搭上了更老的父亲

————————

　来个又水又裸的题    

#include<bits/stdc++.h>
using namespace std;
struct VVV{
    int TO,NE;
}bian[50100];
int Head[10100],dfn[10100],low[10100],stac[10100];
bool instac[10100];

void addd(int u,int v,int cnt)
{
    bian[cnt].NE=Head[u];bian[cnt].TO=v;Head[u]=cnt; 
}
int num=0,top=0,sum=0;
void tar(int root)
{
//    cout<<"YOL:"<<root<<endl;
//    for(int i=1;i<=top;++i)
//    {
//        cout<<stac[i]<<" ";
//    }cout<<endl;
    stac[++top]=root;
    instac[root]=1;
    dfn[root]=low[root]=++num;
    for(int i=Head[root];i;i=bian[i].NE)
    {
        int v=bian[i].TO;//cout<<" VV: "<<v<<" ";
        if(!dfn[v])
        {
            tar(v);
            low[root]=min(low[root],low[v]);
        }
        else if(instac[root])
        {
            low[root]=min(low[root],dfn[v]);
        }
    }
    if(dfn[root]==low[root])
    {
        int _top=top;
        while(stac[top]!=root)
        {
            instac[stac[top]]=0;top--;    
        }
        instac[root]=0;
        top--;
        if(_top-top>1)sum++;
    }
}
int main()
{
    int n,m,x,y;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        addd(x,y,i);
    }
    for(int i=1;i<=n;++i)
    {
        if(!dfn[i])
        {
            tar(i);
        }
    }
    printf("%d",sum);
//    for(int i=1;i<=n;++i)
//    {
//        cout<<dfn[i]<<"  "<<low[i]<<endl;
//    }
    return 0;
}

这可是老爷子成名之作，有不少大大的用处；

还可以有桥，割顶，和a series of 玄学优化

想（xue）更（hui）了再写吧。。。