What is Tarjan?
Tarjan,是一种用来解决图的联通性的一种有效途径，它的一般俗称叫做：缩点。我们首先来设想一下：
如果我们有一个图，其中A,B,C构成一个环，那么我们在某种条件下，如果按照手推的话，会把这3个点当做一个点去处理。
Tarjan就是实现“把多个点当成一个点”的有力工具。而在最前的，就是这个环的判别。或者说强联通分量的判别。那么首先我们要知道：什么是强联通分量。
我们是这么定义的：简单的来说，如果两个点可以直接通达，那么这两个点就是强联通。如果一个有向图的任意两个点之间都满足强联通，那么我们称这个图为强联通图，而一个图的每一个强联通子图成为这个图的强联通分量。（嗯，很好理解呢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