Tarjan的缩点&&割点概述

$What$ $is$ $Tarjan?$

Tarjan,是一种用来解决图的联通性的一种有效途径，它的一般俗称叫做：$\color{red}\text{缩点}$。我们首先来设想一下：

如果我们有一个图，其中$A,B,C$构成一个环，那么我们在某种条件下，如果按照手推的话，会把这$3$个点当做一个点去处理。

$Tarjan$就是实现$\color{red}\text{“把多个点当成一个点”}$的有力工具。而在最前的，就是这个环的判别。或者说强联通分量的判别。那么首先我们要知道：什么是强联通分量。

我们是这么定义的：简单的来说，如果两个点可以$\color{red}\text{直接通达}$，那么这两个点就是$\color{red}\text{强联通}$。如果一个有向图的任意两个点之间都满足强联通，那么我们称这个图为$\color{red}\text{强联通图}$，而一个图的每一个强联通子图成为这个图的$\color{red}\text{强联通分量}$。（嗯，不是很好理解呢$qwq~~$）。我们举一个栗子：

我们可以知道：在这个图里面，${1,2,3,4}$之间是相互联通的，${6},{3}$之间是 相互联通的，那么这三个集合就是图的强联通分量，当然在这里面也包括了 ${1,4}$的强联通，${2,5}$的强联通等等。。。。

当然，$Tarjan$用来解决的是有向图，比如：刻录光盘，间谍网络，等之后会在该blogs里面提到。然后建议大家去做一下Tarjan的模板题：牛的舞会。

要点二：$Tarjan$算法是基于$DFS$来形成的！

我们把该有向图当中的一个子图作为一颗树来进行搜索，把每一个没有被搜索过的点入栈，回溯时判断栈顶到栈底的节点是不是一个强连通分量。

接下来举一个栗子来讲解$Tarjan$的过程。在讲解过程中有几个元素：

$Yeasion[i]$：$i$的搜索顺序，我们称为DFS序。 （DFN）

Nein[i] ：表示i通过非父子关系所能够回到的Yeasion最小的节 点的Yeasion（LOW）

过程如下：

1.碰到一个节点，判断是不是走过（看有没有Yeaison序），若没有走过，进栈stack。

2.若此点有出度，就继续往下找，直到找到底为止，而且每次都返回上来看一看子节点和当前节点的Nein值，并取最小值。

3.如果Yeasion[ ]==Nein[ ]，那么表明当前节点是强联通分量的根节点（因为Nein最小），那么我们就将当前stack里的元素全部弹出，进行缩点。

然后下面搞一组样例模拟一下整个过程：

1 2

2 3

3 6

2 5

5 1

1 4

4 5

我们稍稍画一下图：

首先，我们来到1节点，然后定义一个ken用来记Yeaison。

首先， 我们更新1节点的Yeasion[1]=Nein[1]=++ken;

然后入栈。stack[++top]=1; insta[1]=1;

发现1连接4与2，然后找到2，继续进行。Yeasion[2]=Nein[2]=++ken;

stack[++top]=2;insta[2]=1; 然后继续到3。Yeasion[3]=Nein[3]=++ken; 　

stack[++top]=3;insta[3]=1; 然后继续到6。Yeasion[6]=Nein[6]=++ken;

stack[++top]=6;insta[6]=1;然而接下来我们发现6没有别的节点了，然后就进行判断：

Yeasion[6]==Nein[6]，然后我们··进行退栈操作。然后退完了6。那么我们就把6单独缩成了一个点。然后回溯回到3，我们再进行判断，Yeasion[3]==Nein[3]，然后我们继续退栈，然后我们就把3单独缩成了一个点。然后继续回溯到2，发现2还有5没有走，然后我们再走5。 Yeasion[5]=Nein[5]=+ken; stack[++top]=5; insta[5]=1; 然后发现6可以进行到1和6，然后我们就跑到1，然后回来更新.

Nein[5]=min(Nein[5],Nein[1])=1;之后我们在进行判断的时候发现: Yeasion[5]!=Nein[5],所以不进行退栈.

然后6也遍历过了，然后继续回到了2，然后更新Nein[2]=min(Nein[2],Nein[5])=1，然后也不进行退栈。

再退到1，发现1连接着4，再对4进行Yeasion[4]=Nein[4]=++ken;stack[++top]=4;insta[4]=1;

然后发现1和5都遍历过了，所以判断Yeasion[4]==Nein[4],然后进行退栈，将仍然在栈中的{1,2,4,5}缩成一个点。

至此，Tarjan的模拟就到这。然后缩点又该怎么缩呢？？

我们就考虑再建一个新图，而新图又怎么利用旧图来建呢？

很简单，我们定义一个belong[ ]，一个tot[ ]分别用来记录：原图中的i节点属于新图中的哪一个节点，和新图中的节点的权值。在进行缩点的时候，我们将所有栈中的元素pass进行退栈,然后定义的新图点数cnt++;然后：pass=stack[top--]; belong[pass]=cnt; tot[cnt]+=value[pass]; insta[pass]=0; 基本的操作就是这样，当然这个退栈循环的条件只有一个：pass不等于当前节点，这也就是为什么{6},{3}会单独缩成一个点的原因。因为我们退栈的判断是Yeasion==Nein，也就是根节点，所以我们退栈也只退到当前的强联通分量的根节点：当前节点。

下面是代码咯：

define MAXN 100010

struct point{//第一个struct 表示原图
int from;
int to;
int next;
}edge[MAXN];
int head1[MAXN],total;
void add(int f,int t){//原图的建图过程
total++;
edge[total].from=f;
edge[total].to=t;
edge[total].next=head[f];
head[f]=total;
}
struct point2{//第二个struct 表示新图
int from;
int to;
int next;
}e[MAXN];
int head2[MAXN],total2;
void add2(int f,int t){//新图的建图过程
total2++;
e[total2].from=f;
e[total2].to=t;
e[total2].next=head2[f];
head2[f]=total2;
}
int Yeasion[MAXN],Nein[MAXN];
//Yeasion[i]表示搜索顺序，即DFS序
//Nein[i]表示i节点通过非父子关系所能够回溯到的最早的节点的dfs序
int belong[MAXN],value[MAXN];
//belong[i]表示旧图中的节点i在新图中属于那一个节点
//value[i]表示旧图中的节点i的权值
int tot[MAXN],cnt
//tot[i]表示新图中的节点权值
//cnt表示新图中的节点数
int stack[MAXN],top,ken;
//stack栈，top栈顶，ken表示搜索的深度
bool insta[MAXN];//在栈中
void Tarjan(int now){
Yeasion[now]=Nein[now]=++ken;
//先进行更新
stack[++top]=now; insta[now]=1;
//入栈
for(int i=head[now];i;i=edge[i].next){
//枚举和now节点相连的所有的边
if(!Yeasion[edge[i].to]){
//如果和now相连的点没有被访问过
Tarjan(edge[i].to);
//Tarjan一遍。这也就是体现深搜性质的地方
Nein[now]=min(Nein[now],Nein[edge[i].to]);
//对now的Nein值进行更新
}else if(insta[edge[i].to])
//如果被访问过并且依然在栈中
Nein[now]=min(Nein[now],Nein[edge[i].to]);
//再进行一遍更新
}
if(Yeasion[now]==Nein[now]){
//发现找到了根结点
cnt++; int pass;
//新图中新增一个节点
//定义一个过去节点，用以表示栈中元素。
do{
pass=stack[top--];
belong[pass]=cnt;
tot[cnt]+=value[pass];
insta[pass]=false;
//缩点过程
}while(now!=pass);
//我们缩的当前这个点最多只能到包含根结点
}
}
然后在这之后，我们需要将新图中的节点连接起来，然后我们就有了一个link()函数。

int ind[MAXN],oud[MAXN];//入度出度，很多时候会用到的
void link(){
for(int i=1;i<=n;i++)
for(int j=head[i];j;j=edge[j].next)
if(belong[i]!=belong[edge[j].to]){
add2(belong[i],belong[edge[j].to]);
ind[belong[edge[j].to]]++;
oud[belong[i]]++;
}
}
Tarjan的缩点过程其实大概就是这个样子。而Tarjan在真实例题中的应用其实大多数是这个：将有向有环图转化为有向无环图，即DAG图，然后我们就可以在这个DAG上面进行DP,拓扑排序等一系列的操作。不然大可以想一想：你怎么在一个有向有环图上跑这些东西呢？？

然而其实也不乏有专门直接考关于Tarjan的题。而大家要记住了：这里的Tarjan缩的是点啊！也就是说如果你有一个带的是边权的图，那Tarjan就凉凉了。 接下来附上几道关于Tarjan在缩点方面应用的好♂题（emmm）：

[模板]缩点

[USACO]校园网络

[国家集训队]稳定婚姻

[APIO2009]抢掠计划 （个人题解）

[JSOI2010]连通数 （个人题解）

[SDOI2010]所驼门王的宝藏 （个人题解）

嗯，个人觉得刷完这些题Tarjan缩点方面大概是没有什么很大的问题了。

然后是第二个内容：

割点

这里引入了一个新的概念：什么叫“割点”呢？？

就是说，在当前这个连通图里面，如果去掉了这个点集合以及这个点集合所相连的所有的边，就可以使这个图不连通。那么我们就把这个点集合叫做这个图的割点集合（割顶）。下面举一个栗子：

在这张图里面，假如我们去掉了2节点及其所有的边，或者说去掉了3节点及其所有的边，那么整个图就会变得不连通。 那么2节点和3节点就是这张图的割点。由此可见：一张图的 割点可能有很多个。割点集合的元素可能不止一个，也可能有很多个集合。

而对于割点的寻找，这里我们用一种类似于刚刚的Tarjan的方法来进行。什么叫“类似”呢，就是说我们在这里肯定不需要用到缩点，但是其遍历方法或者说思路确实十分相像。

然后我们再引入一个概念：“割边”。同割点。在当前这个连通图里面，如果去掉了这个边集合，就可以使这个图不连通。那么我们就把这个边集合叫做这个图的割边集合。我们可以知道在这个图里面2<——>3边是一个割边，因为去掉这条边之后我们的整个图就变得不连通了。当然，{2<——>3,2<——>4}也是一个割边集合只不过元素比上一个多了一个而已。由此可见：一张图的割边可能有很多个。割边集合的元素可能不止一个，也可能有很多个割边集合。

在这里我们先引入几个概念：

1.点连通度：最小割点集合中的顶点数。

以下图为例，我们发现，如果在这个图里面删去了{3,4}节点，那么图就会变得不连通，而 如果删除了{3,4,5}，图也会不连通。

然后我们发现在这些割点集合 中最小的就是{3,4}。那么该图的点连通度就是2。

2.边连通度：最小割边集合中的边数。在这个图里面边连通度也是2。

3.点双联通图：如果一个无向图的点联通度>1，那么这个图是点 双联通图。！在点双连通图里面没有割点！。只有在点连通度==1的时候， 原图才有割点。

4.边双连通图：同点双联通图。边双联通图里面没有桥。（唯一割边）

给出两个猜想：

1.两个割点之间的边一定是割边。

2.割边的两个端点一定是割点。

emmmmm然而并不对... 以上是一个经常犯的误区。

求割点的方法其实和Tarjan的缩点很相似。

我们知道，缩点是建立在DFS的基础上的。大家还记得这个图吧，（下）我们就利用这个图建立了一个DFS树。

这就是我们的DFS树。（下）

我们可以定义出三种边：

1.树枝边：DFS经过的边。即DFS搜索树上的边。

2.前向边：与DFS方向一致的边。如右图的{1,2},{2,3},{3,6},{1,4},{2,5}。

3.后向边：与DFS方向相反的边。如右图的{5,1}边。

同缩点一样，我们依然定义一个时间戳Yeasion[ ]，一个Nein[ ] 为now子树中的节点经过最多一条后向边能追溯到的最早的树中 节点的序号（解释变了一变，其实一样啦~qwq）

在这个Tarjan函数中我们一共有两个变量，一个是now表示当前节点，一个是fa表示父亲节点。在这个函数的开头我们要定义一个child用来记录当前节点的子树个数。因为对于割点的判断，我们要分成两种来看：

1.是根节点。那么我们就看它的子树个数，如果超过了两个，那么它肯定是割点。

2.非根节点。对于边(now,edge[i].to)，如果Nein[edge[i].to]>Yeasion[now],那么它就是割点。（至于原因嘛.....嘿嘿）。

所以在循环边的时候，如Nein[edge[i].to]>Yeasion[now]并且now!=fa，那么它就是割点咯。

然后如果now==fa那么child++;然后这个外面我们的更新就和缩点不一样了，这里的更新是：Nein[now]=min(Nein[now],Yeasion[edge[i].to]);并

且我们也不需要stack，因为我们不需要缩点。

然后在循环外面我们还要判断now!=fa并且child>=2的时候，它也是割点。

然后代码如下啦：

define MAXN 100010

int Yeasion[MAXN];
int Nein[MAXN],ken;
//和原来一样
bool cut[MAXN];//cut[i]表示i节点是否是割点
int n,m,total,head[MAXN];
struct point{//图
int from;
int to;
int next;
}edge[MAXN*100];
void add(int f,int t){//前向星存图
total++;
edge[total].from=f;
edge[total].to=t;
edge[total].next=head[f];
head[f]=total;
}
void Tarjan(int now,int fa){
Yeasion[now]=Nein[now]=++ken;
int child=0;//记录now节点的子树个数
for(int i=head[now];i;i=edge[i].next){
if(!Yeasion[edge[i].to]){
Tarjan(edge[i].to,fa);
Nein[now]=min(Nein[now],Nein[edge[i].to]);
if(Nein[edge[i].to]>=Yeasion[now])
if(now!=fa) cut[now]=1;
if(now==fa) child++;
}
Nein[now]=min(Nein[now],Yeasion[edge[i].to]);
}if(child>=2&&now!=fa){
cut[now]=1;
}
}
然后接下来是求点双连通分量。其实很简单，在刚刚的代码中我们空闲了一个stack没有用，在这里就派上用场了。

在每一次我们遇到一条树枝边或者后向边的时候，我们就将这条边加入栈中。所以每一次遇到满足Yeasion[now]<=Nein[edge[i].to] 的时候，说明now是一个割点，然后我们就把当前还在栈中的元素一个个取出，直到遇到边{now,edge[i].to}为止。然后我们取出的这些边与其相连的点，就构成了一个点双连通分量。（注意是存边不是点！） 对于边双连通分量，其实更简单，我们将找到的所有的桥删去，然后剩下的就是边双连通分量。

然后关于割点的例题也不是很多，我在这里就且放上三道吧！

【模板】割点（割顶）

[POI2008]BLO-Blockade

[HNOI2012]矿场搭建

嗯，然后关于Tarjan的缩点&&割点应用概述就到此为止，如果有错误或是不懂的地方欢迎批评指正！

————Yeasion_Nein