文章目录 一、tarjan求强连通分量1：算法流程2：模板 二、tarjan缩点1：相关定义2：算法流程 三、tarjan求割点、桥1、什么是割点2.割点怎么求？3。割点tarjan模板&运行实例
tarjan可以做什么？
根据 Robert Tarjan 的名字命名的算法Tarjan算法可以在线性时间内求出无向图的割点与桥，再进一步的求出双联通分量，也在数据结构上做出了贡献。
Tarjan算法的用途
求桥和割点
求点和边的双连通分量
.求强连通*
参考博客：[tarjan算法入门](https://blog.csdn.net/acmmmm/article/details/16361033)[tarjan算法入门](https://www.luogu.com.cn/blog/wyz598085788/solution-p3627)[tarjan算法详解](https://blog.csdn.net/hurmishine/article/details/75248876?depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-20&utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-20)[tarjan缩点](https://blog.csdn.net/li1615882553/article/details/79760325?depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-4&utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-4)[tarjan求割点](https://www.cnblogs.com/collectionne/p/6847240.html)[targan相关定义](https://www.cnblogs.com/stxy-ferryman/p/7779347.html)[tarjan寻找割点与桥](https://blog.csdn.net/qq_43326267/article/details/88561434?depth_1-utm_source=distribute.pc_relevant.none-task-blog-OPENSEARCH-18&utm_source=distribute.pc_relevant.none-task-blog-OPENSEARCH-18) 一、tarjan求强连通分量 1：算法流程引用来自度娘的一句话：
“有向图强连通分量：在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量(strongly connected components)。”
反正就是在图中找到一个最大的图，使这个图中每个两点都能够互相到达。这个最大的图称为强连通分量，同时一个点也属于强连通分量。
tarjan算法，之所以用DFS就是因为它将每一个强连通分量作为搜索树上的一个子树。而这个图，就是一个完整的搜索树。
为了使这颗搜索树在遇到强连通分量的节点的时候能顺利进行。每个点都有两个参数。
1，DFN［］作为这个点搜索的次序编号（时间戳），简单来说就是 第几个被搜索到的。％每个点的时间戳都不一样％。
2，LOW［］作为每个点在这颗树中的，最小的子树的根，每次保证最小，like它的父亲结点的时间戳这种感觉。如果它自己的LOW［］最小，那这个点就应该从新分配，变成这个强连通分量子树的根节点。
ps：每次找到一个新点，这个点LOW［］＝DFN［］。
而为了存储整个强连通分量，这里挑选的容器是，堆栈（栈中所有点一定是有父子关系的）。每次一个新节点出现，就进站，如果这个点有 出度 就继续往下找。直到找到底，每次返回上来都看一看子节点与这个节点的LOW值，谁小就取谁，保证最小的子树根。如果找到DFN［］＝＝LOW［］就说明这个节点是这个强连通分量的根节点（毕竟这个LOW［］值是这个强连通分量里最小的。）最后找到强连通分量的节点后，就将这个栈里，比此节点后进来的节点全部出栈，它们就组成一个全新的强连通分量。
2：模板 #define MAX 10005#define ll long longvector<ll> g[MAX];ll color[MAX], vis[MAX], stack[MAX], dfn[MAX], low[MAX], cnt[MAX];//deep:节点编号 top：栈顶 sum：强连通分量数目ll deep, top, sum, res = 0;void tanjan(ll v) {dfn[v] = ++deep;low[v] = deep; //(1)初始化dfn数组，同时将low设置为相同值vis[v] = 1;stack[++top] = v;//(2)入栈，作为栈顶元素，同时更新vis数组for (unsigned i = 0; i < g[v].size(); i++) {//(3)遍历所有可能到达的点ll id = g[v][i];if (!dfn[id]) {//如果这个点从没访问过，则先放问它，再用它更新low[v]的值tanjan(id);low[v] = min(low[v], low[id]); //他的儿子如果能连到更小的祖先节点，显然他也可以}else {if (vis[id]) {//不在栈中的点，要么没有访问，要么不能到达id，所以只需要判断栈中的low[v] = min(low[v], low[id]);}}}if (low[v] == dfn[v]) {//(4)自己和子节点形成了强连通分量，或者只有自己孤身一人color[v] = ++sum;vis[v] = 0;while (stack[top] != v) {//将从v开始所有的点取出color[stack[top]] = sum;//给予同一颜色vis[stack[top--]] = 0;//出栈要顺便修改vis}top--;}} 二、tarjan缩点 1：相关定义其实这也是利用了tarjan求强连通分量的方法，对于一些贡献具有传导性，比如友情啊、路径上的权值啊等等非常适用。
思想就是因为强连通分量中的每两个点都是强连通的，可以将一个强连通分量当做一个超级点，而点权按题意来定。
首先我们先看一下一个问题：一个有向图，有n个点以及m条边，我们至少应该添加几条边才能使整个图变成强连通图。或者是一个无向图至少添加几条边变成连通图。
首先我们对于一个有向无环的图（DAG），至少添加几条边才能使它变为强连通图？我们很容易根据有向无环图的性质得到，我们计算入度为零的点数为a，出度为零的点数为b，那么我们至少需要添加的边数为max(a,b)，如果只有一个点的话，我们不需要添加任何边。
那么我们怎么把一个图转换为DAG呢，因为上面给出的图可能存在环，那么我们就会想到把已经组成全连通的子图转换成一个点来看，那么我们最终的图就不会包含环了。
好了，解决这类问题的思路已经想好了，下面我们来进行求解：
我们使用Tarjan算法求解出强连通分量之后，我们上面使用了一个color数组将同一个连通分量的点分配相同的数值，然后我们再次遍历一遍所有的边，如果边的两侧u->v不属于同一颜色，那么u对应颜色将会有一条边连向v对应的颜色。在此基础上我们可以计算缩点之后的出入度，得到max(a,b)或者其他一些信息。
2：算法流程其实我们上述的tarjan算法已经求出了每个点属于的color,其实每个color就代表了一个最大联通集，
#define MAX 10005#define ll long longvector<ll> g[MAX];ll color[MAX], vis[MAX], stack[MAX], dfn[MAX], low[MAX], cnt[MAX], num[MAX];ll ind[MAX], outd[MAX];//每个点的出度入度//deep:节点编号 top：栈顶 sum：强连通分量数目ll deep, top, sum, res = 0;void tanjan(ll v) {dfn[v] = ++deep;low[v] = deep; //(1)初始化dfn数组，同时将low设置为相同值vis[v] = 1;stack[++top] = v;//(2)入栈，作为栈顶元素，同时更新vis数组for (unsigned i = 0; i < g[v].size(); i++) {//(3)遍历所有可能到达的点ll id = g[v][i];if (!dfn[id]) {//如果这个点从没访问过，则先放问它，再用它更新low[v]的值tanjan(id);low[v] = min(low[v], low[id]); //他的儿子如果能连到更小的祖先节点，显然他也可以}else {if (vis[id]) {//不在栈中的点，要么没有访问，要么不能到达id，所以只需要判断栈中的low[v] = min(low[v], low[id]);}}}if (low[v] == dfn[v]) {//(4)自己和子节点形成了强连通分量，或者只有自己孤身一人color[v] = ++sum; num[sum]++; //num统计该颜色有多少点vis[v] = 0;while (stack[top] != v) {//将从v开始所有的点取出color[stack[top]] = sum;//给予同一颜色vis[stack[top--]] = 0;//出栈要顺便修改visnum[sum]++;}top--;}}int main(){for (int i = 1; i <= N; i++) {for (unsigned k = 0; k < g[i].size(); k++) {ll v = g[i][k];if (color[v] != color[i]) {//二者分属于不同的联通集outd[color[i]] += 1; //以颜色作为点，更新相应点的出度}}}} 三、tarjan求割点、桥 1、什么是割点在无向连通图中，如果将其中一个点以及所有连接该点的边去掉，图就不再连通，那么这个点就叫做割点（cut vertex / articulation point）。
例如，在下图中，0、3是割点，因为将0和3中任意一个去掉之后，图就不再连通。如果去掉0，则图被分成1、2和3、4两个连通分量；如果去掉3，则图被分成0、1、2和4两个连通分量。
如果我们去掉点1，图分为2 - 5 - 4 - 3 - 2和6 - 7 - 8+9两个子图；去掉点6，图分为1 - 2 - 3 - 4 - 5、7 - 8和9三个子图。所以点1 、6为这个图的两个割点。
与之前强连通分量中的tarjan差不多。但要加一个特判，
首先选定一个根节点，从该根节点开始遍历整个图（使用DFS）。
对于根节点，判断是不是割点很简单——计算其子树数量，如果有2棵即以上的子树，就是割点。因为如果去掉这个点，这两棵子树就不能互相到达。（注意这里的概念，称之为子树，表示了子树互不相连，而且不连向祖先）
对于非根节点，判断是不是割点就有些麻烦了。我们维护两个数组dfn[]和low[]（就是上面用过的），对于边(u, v)，如果low[v]>=dfn[u]，此时u就是割点。这是我认为最难以理解的一部分，可以这样想：low[v]>=dfn[u]也就意味着，v不能回到u的前面，这是一种什么情况呢？
显然如果节点U的所有孩子节点可以不通过父节点U而访问到U的祖先节点,那么说明此时去掉节点U不影响图的连通性,U就不是割点。
相反,如果节点U至少存在一个孩子顶点，必须通过父节点U才能访问到U的祖先节点,也就是如果存在一个孩子low[v]>=dfn[u]，那么去掉节点U后，顶点U的祖先节点和孩子节点就不连通了,说明U是一个割点。
ps：无向图一定要注意回边的存在
争议点：
关于tarjan算法，一直有一个很大的争议，就是low[u]=min(low[u],dfn[v]);（你可以发现这和上面求强连通分量是不一杨的）
这句话，如果改成low[u]=min(low[u],low[v])就会wa掉，但是在求强连通分量时却没有问题
根据许多大佬的观点，我想提出自己的一点看法，在求强连通分量时，如果v已经在栈中，那么说明u，v一定在同一个强连通分量中，所以到最后low[u]=low[v]是必然的，提前更新也不会有问题，但是在求割点时，low的定义有了小小的变化，不再是最早能追溯到的祖先，（因为是个无向图）没有意义，应该是最早能绕到的割点，为什么用绕到，是因为是无向边，所以有另一条路可以走，如果把dfn[v]改掉就会上翻过头，可能翻进另一个环中，所以wa掉，仅是本人的一些个人看法，不知道讲的对不对，请各位指教。
3。割点tarjan模板&运行实例 // v:当前点 r：本次搜索树的rootvoid tarjan(ll u, ll r) {dfn[u] = low[u] = ++deep;ll child = 0;for (unsigned i = 0; i < g[u].size(); i++) {ll v = g[u][i];if (!dfn[v]) {tarjan(v, r);low[u] = min(low[u], low[v]);if (low[v] >= dfn[u] && u != r)cut[u] = 1;//不是根而且他的孩子无法跨越他回到祖先if (r == u)child++; //如果是搜索树的根，统计孩子数目}low[u] = min(low[u], dfn[v]);//已经搜索过了}if (child >= 2 && u == r)cut[r] = 1;}
对如上的图我们来跑一次算法，深入理解以下算法的含义