图的桥-tarjan算法求图的桥

求图的桥和求图的割点差不多，只是判断条件改为：low[i]>num[cur] ,即顶点i无法回到祖先，也没有另外一条路可以回到父亲，则cur-i是桥

核心代码

void dfs(int* num,int* low,int** arr,int cur, int father)
{
	index++;//时间戳增加

	num[cur] = index;//记录当前节点的时间戳
	low[cur] = index;//记录当前节点所能回溯的最早时间戳，最开始当然是自己

	for (int i = 1; i <=point; i++)//枚举与当前顶点相邻接的顶点
	{
		if (arr[cur][i]==1)//如果两个顶点相邻接
		{
			if (num[i] == 0)//如果顶点i的时间戳为0，则顶点i还没有被访问过
			{
				dfs(num, low, arr, i, cur);//访问顶点i，顶点i的父亲是当前顶点
				low[cur] = min(low[cur], low[i]);//顶点i访问完后，顶点i也有了自己的时间戳，此时更新当前顶点所能回溯的最早时间戳

				//在当前顶点不是根节点的情况下
				//如果存在顶点i无法回溯到当前顶点，也无法回溯到祖先，则cur-i是割边
				if (cur != root && low[i] > num[cur])
				{
					cout << cur << "-" << i << endl;
				}
			}
			//如果顶点i被访问过，且i不是当前顶点的父亲
			//则i是当前顶点的祖先，更新当前顶点所能回溯的最早时间戳
			else if (i != father)
			{
				low[cur] = min(low[cur], num[i]);
			}
		}
	}

	return;

}

整体代码：

#include<iostream>
using namespace std;

int point, edge;//点数和边数
int root = 1;//默认根节点为1
int index = 0;

void dfs(int* num,int* low,int** arr,int cur, int father)
{
	index++;//时间戳增加

	num[cur] = index;//记录当前节点的时间戳
	low[cur] = index;//记录当前节点所能回溯的最早时间戳，最开始当然是自己

	for (int i = 1; i <=point; i++)//枚举与当前顶点相邻接的顶点
	{
		if (arr[cur][i]==1)//如果两个顶点相邻接
		{
			if (num[i] == 0)//如果顶点i的时间戳为0，则顶点i还没有被访问过
			{
				dfs(num, low, arr, i, cur);//访问顶点i，顶点i的父亲是当前顶点
				low[cur] = min(low[cur], low[i]);//顶点i访问完后，顶点i也有了自己的时间戳，此时更新当前顶点所能回溯的最早时间戳

				//在当前顶点不是根节点的情况下
				//如果存在顶点i无法回溯到当前顶点，则cur-i是割边
				if (cur != root && low[i] > num[cur])
				{
					cout << cur << "-" << i << endl;
				}
			}
			//如果顶点i被访问过，且i不是当前顶点的父亲
			//则i是当前顶点的祖先，更新当前顶点所能回溯的最早时间戳
			else if (i != father)
			{
				low[cur] = min(low[cur], num[i]);
			}
		}
	}

	return;

}

int main()
{
	cin >> point >> edge;

	int** arr = new int*[point + 1];//图数组
	int* num = new int[point + 1];//时间戳数组
	int* low = new int[point + 1];//回溯时间戳数组
	//初始化邻接矩阵，各个数组
	for (int i = 0; i <= point; i++)
	{
		arr[i] = new int[point + 1];
		for (int j = 0; j <= point; j++)
		{
			arr[i][j] = 0;
		}
		num[i] = 0;
		low[i] = 0;
	}

	//录入边的信息
	int a, b;
	for (int i = 0; i < edge; i++)
	{
		cin >> a >> b;
		arr[a][b] = 1;
		arr[b][a] = 1;
	}
	//dfs
	dfs(num,low,arr,1, root);

	delete[] arr;
	delete[] num;
	delete[] low;
	return 0;
}