tarjan算法

时间戳：用一个计数变量表示时间，一个数组记录到达该点时的时间，每访问到一个新的点时间戳+1；

tarjan算法的核心思想是：如果当前点是我们访问到的一个连通分量中的第一个点，那么之后的点一定访问不到该点之前的时间戳，而且该点之后处于同一连通分量中的点能访问到的最小时间戳就是该点的时间戳。

如上图所示（有点丑），红色为该点的时间戳，蓝色为其他图中的边，绿色为该点能到达的最小时间戳。

计算方程：最小时间戳（u）=min(u的时间戳，所有u能到达的点v中的 最小时间戳（v）{v没有分配到某个联通分量 } )；

实现：用lowbit记录某点能访问到的最早时间，time记录该点的时间戳。

每到达一个点把该点压入栈，标记vis。

如果lowbit==time则该点就是这个连通分量中的第一个点，而其他点一定能访问到他。所以一直pop直到该点被弹出。（弹出来的都属于这个连通分量）

如果不懂可以自己画个图手动模拟一下感受感受。

如下情况 2 -> 1 ,从1开始DFS一次，2开始DFS一次，一定要区分这两次，mint不要混了！

还有！DFS链必须是自己的DFS链

int sta[N],top,ltcnt,size[N],mint[N],tcnt,belong[N];
void DFS(int u){
    int now=++tcnt;mint[u]=now;sta[++top]=u;
    for(int i=head[u];i;i=e[i].next){
        if(belong[e[i].t]!=0) continue;
        if(mint[e[i].t]==0) DFS(e[i].t);
        mint[u]=min(mint[u],mint[e[i].t]);
    }
    if(mint[u]==now){
    ltcnt++;
    while(sta[top]!=u) size[ltcnt]++,belong[sta[top--]]=ltcnt;
    size[ltcnt]++,belong[sta[top--]]=ltcnt;
    }
}

2016-02-10

这几天开始学图的连通了（因为发现这是个大坑，好像很基础，但我不会）。于是就神神奇奇地开始写缩点了，但貌似调了一个晚上。所以觉得还是写一下总结总结比较不错。

先说一下什么是连通吧：

如果点A可以通过某条神奇的小道到达B，而B也可以一阵乱走走到A，那么A、B是连通的。无向肯定不用说，毕竟可以原路返回，所以两点一定连通。

连通图的定义：如果该图中任意两点都连通，则这个图是个连通图。（如果这是个有向图，还可以叫强连通图。反正有“强”的就是针对有向图的。）

（强）连通分量是什么呢？就是一个图中的尽量多的互相连通的一些点构成的一个子图呗。

如下图中橘黄色圈出来的是两个强连通分量：

（单个的1算不算？可以不用纠结，没人会考你这个。）

好了，来讲下最常用的缩点吧！

有两种缩点的方法：

1、一种是kozaraju提出的。（别问我怎么念）

2、tarjan提出。（跟我念塔儿尖）

kozaraju

(不知道他当初是怎么脑洞大开想到的)
图中橘黄色圈出的为强连通分量，蓝色是标号，红色是连通分量之间的边。

图中橘黄色圈出的为强连通分量，蓝色是标号，红色是连通分量之间的边。

如果我们在一个连通分量里一阵DFS乱搜，肯定能把该连通分量内的所有点搜出来，但是肯定会混杂一些其他的点。但如果我们有顺序地搜，比如从3中任意一个点开搜，肯定会刚好把3这个连通分量的所有点搜出来，记录以及标记；然后是2，1，5，4；

是不是有点拓扑顺序的感觉？

对的就是这样，所以他采用的DFS版的拓扑序。但是这个图毕竟有环，连通分量自己内部的情况太复杂——

比如这样

如果从1开始搜，你会很愉快地先把3加入拓扑序列。

拓扑序乱了怎么办呢？没有关系，看之前在DFS版拓扑中说的——现在正在访问的点永远会比它可以到达的点先输出。

我们能够保证1所在连通块总有一个点会比其他连通块中的点后出现在拓扑序列中。

没看懂？接下来更详细讲解。（其实这个方法不常用，可以略过）

上图中ABC分别代表三个连通分量

一下以abc代表三个对应连通分量中的点

我们希望得到的顺是CBA，按照这个顺序可以放心地顺着乱搜

如果我们从BAC的顺序(随机)开始生产拓扑序（注意是

我不得不得不说这是一种神奇拓扑序生成方式。

我们沿着有向边反着走，假设我们搜索到了u，那么下一步会搜索所有指向u的点,因为只要这些点存在就还不能把u加入拓扑序中。

思路如下：

function DFS(int u){
    for(所有通过有向边可以到达u的点v){
        如果v没有被删掉
                    DFS(v);//访问完后v会被删掉
    }
    把u加入拓扑序中
    删掉当前点u（可以采用打标记的方式）
}

当然我们还可以开一下脑洞

为什么不能就顺着来呢？然后把得到的拓扑序列反转呢！

事实证明这是可以的。poj2367板题可以过。（有special judge）

那么我们还是来证明一下正确性吧：

对于原拓扑序列，该序列只有一个要求及：如果u是v的祖先（反着就是有一条从u到v的路径），那么在拓扑序中u必须比v先出现，而DFS就可以满足这个需求，在递归完成之前是绝不会被输出的，而该点的DFS可以访问到它所有的祖先。而现在我们把图正向序列反向也可以保证子孙先比祖先后出现。现在正在访问的点永远会比它可以到达的点先输出。

速度上这个办法的常数是明显大于常规拓扑排序的。

2016-02-05

对偶图是建立在原有的平面图上的。

对于为什么叫对偶图，先看下度娘对于对偶的解释：

对偶是用字数相等、结构相同、意义对称的一对短语或句子来表达两个相对应或相近或意思相同的修辞方式。

自己可以看完对偶图的建图之后再来琢磨下这个句子，脑补一下对偶图的对偶

好了，说正事。

这是一张对偶前的平面图

红线组成的是它的对偶图

什么？不知道怎么画？

就是把面变成点，相邻的面连边。（所以每一条边都会跨国原有边界。）

so,我们现有一个平面图

然后再找出图上所有面（还有最外面无限大的面）

然后，把面看成点

就像之前说的，相邻的面连边，蓝色与红色和紫色还有灰色相连（只有一个定点相同的不算，如绿色和蓝色）

然后连下去

就画好了

那么有什么用呢

比如最小割之类的啊

如果左上和右下分别为源点（S）和汇点（T），那么如果我们把外侧无限大的面分成两个 半面，（忽略无限大面自己之间的连线），构造对偶图，那么对偶图中灰蓝色点到灰紫色点的的任意一条路径都是原图的一个割。

因为对偶图中的边会跨过切只会跨过原图中的一条边。所以就可以在最短路的时间内跑最小割了。

例题传送门

2016-02-03