文章目录23

文章目录一、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_sourcedistribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-20utm_sourcedistribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-20) [tarjan缩点](https://blog.csdn.net/li1615882553/article/details/79760325?depth_1-utm_sourcedistribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-4utm_sourcedistribute.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_sourcedistribute.pc_relevant.none-task-blog-OPENSEARCH-18utm_sourcedistribute.pc_relevant.none-task-blog-OPENSEARCH-18)一、tarjan求强连通分量1算法流程引用来自度娘的一句话“有向图强连通分量在有向图G中如果两个顶点vi,vj间vivj有一条从vi到vj的有向路径同时还有一条从vj到vi的有向路径则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通称G是一个强连通图。有向图的极大强连通子图称为强连通分量(strongly connected components)。”反正就是在图中找到一个最大的图使这个图中每个两点都能够互相到达。这个最大的图称为强连通分量同时一个点也属于强连通分量。tarjan算法之所以用DFS就是因为它将每一个强连通分量作为搜索树上的一个子树。而这个图就是一个完整的搜索树。为了使这颗搜索树在遇到强连通分量的节点的时候能顺利进行。每个点都有两个参数。1DFN作为这个点搜索的次序编号时间戳简单来说就是 第几个被搜索到的。每个点的时间戳都不一样。2LOW作为每个点在这颗树中的最小的子树的根每次保证最小like它的父亲结点的时间戳这种感觉。如果它自己的LOW最小那这个点就应该从新分配变成这个强连通分量子树的根节点。ps每次找到一个新点这个点LOWDFN。而为了存储整个强连通分量这里挑选的容器是堆栈栈中所有点一定是有父子关系的。每次一个新节点出现就进站如果这个点有 出度 就继续往下找。直到找到底每次返回上来都看一看子节点与这个节点的LOW值谁小就取谁保证最小的子树根。如果找到DFNLOW就说明这个节点是这个强连通分量的根节点毕竟这个LOW值是这个强连通分量里最小的。最后找到强连通分量的节点后就将这个栈里比此节点后进来的节点全部出栈它们就组成一个全新的强连通分量。2模板#define MAX 10005 #define ll long long vectorll 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]) {