企业官网建设流程全解析

文章目录

• 一、tarjan求强连通分量
• • 1：算法流程
  • 2：模板
• 二、tarjan缩点
• • 1：相关定义
  • 2：算法流程
• 三、tarjan求割点、桥
• • 1、什么是割点
  • 2.割点怎么求？
  • 3。割点tarjan模板&运行实例

tarjan可以做什么？

根据 Robert Tarjan 的名字命名的算法Tarjan算法可以在线性时间内求出无向图的割点与桥，再进一步的求出双联通分量，也在数据结构上做出了贡献。

Tarjan算法的用途

1. 求桥和割点

2. 求点和边的双连通分量

3. .求强连通*

   参考博客： [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 long vector<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]) {