文章目录

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]) {//如果这个点从没访问过，则先放问它，再用它更新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 long

vector<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;//出栈要顺便修改vis
			num[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为这个图的两个割点。

2.割点怎么求？

与之前强连通分量中的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：本次搜索树的root
void 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;
}

在这里插入图片描述
对如上的图我们来跑一次算法，深入理解以下算法的含义

  • 我们从1开始运行算法tarjan(1,1)，此时low[1]=dfn[1]=1按照dfs序我们应该遍历到2，此时dfn[2]=low[2]=2，然后2有一条边连向1，dfn[1]!=0因此low[2]=min(low[2],dfn[1])=1。然后2有一条边连向5,dfn[5]=low[5]=3。
  • 开始处理5，5第一条边连向2，更新low[5]=min(low[5],dfn[2])=2，然后tarjan(3,1)，3有一条边连向1，low[3]=1，3有一条边连向5，low[3]=min(low[3],dfn[5])=1，算法返回点5，更新low[5]=min(low[5],low[3])=1，也就是说5可以绕回1点，更新4效果一样不再赘述。
  • 5最后一条边连向6,tarjan(6,1)，6唯一一条边回到5，而且5已经访问过了，因此low[6]=min(low[6],dfn[5])=3注意了注意了，如果这里是low[5]会如何？那么low[6]=1，可以看到对于无向图而言，当点5已经遍历过了，我们不能使用low[5]作为他的儿子能返回的最小祖先，必须使用dfn[5]。此时函数返回5，low[6]>=dfn[5]，说明6不能绕过5前往祖先节点，因此5是一个割点。
  • 函数返回到节点2，2不是根节点，而且他的所有孩子都是low[v]=1，他不是割点。
  • 函数返回到节点2，遍历了2节点，其余所有节点都得到了遍历，因此最多有一个孩子，虽然low[2]>=low[1]，但1是根节点，依然不是割点。显然没有任何节点可以跑到根节点dfn[1]的前面，所以利用low[v]>=dfn[u]判断时一定要保证当前点不是根节点。
# 算法
Logo
GitCode 开源社区

旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。

更多推荐

[转载]在Windows环境下安装GNU Radio

转自：在Windows环境下安装GNURadio_恐弱智_新浪博客GNU Radio是用Python开发的，大部分开源的工程能够在Linux环境下运行良好，而Windows下却运行的很勉强，而且安装配置都很复杂。GNU Radio算是个例外了，不光提供了Windows的二进制安装，还有比较详细的说明。我是Python小白，所以折腾了好久才弄好，特意记录下来，免得以后再装还折腾。GNU Radio的

avatar GitCode 开源社区

centOS 8 使用dnf安装Docker

DNF是什么？CentOS 8使用YUM软件包管理器版本v4.0.4。现在，该版本使用DNF(已删除YUM)。DNF是软件包管理器。它会在Linux发行版上安装，执行更新并删除软件包。使用DNF安装Docker跳过具有损坏依赖性的程序包一个有效的解决方案是使您的CentOS 8系统使用以下--nobest命令安装最符合条件的版本：sudo dnf install docker...

avatar GitCode 开源社区

定时同步数据库表(mysql+linux+crontab)

sync.sh里面的参数需要改变，ip/username/password/database/tablesync.sh#!/bin/sh# Please change the IP and password of the data source db.# Then change the table name.filename=/home/nington/db/$(date +%Y-%m

avatar GitCode 开源社区