AC,但疑惑(是关于重边的问题)
查看原帖
AC,但疑惑(是关于重边的问题)
364848
Bodhi楼主2023/4/2 23:06

RT

第一份代码的tarjan函数(使用边的编号判重):

void tarjan(int x, int frome)//
{
	low[x] = dfn[x] = ++tme;
	int to;
	for (int i = head[x]; ~i; i = e[i].next)
	{
		to = e[i].to;
		if (!dfn[to])
		{
			tarjan(to, i);//
			low[x] = min(low[x], low[to]);
			if (dfn[x] < low[to])
				e[i].flag = e[i ^ 1].flag = true;
		}
		else if (i != (frome ^ 1))//
			low[x] = min(low[x], dfn[to]);
	}
}

第二份的tarjan(使用to!=fa,未使用其他判重方式)

void tarjan(int x, int fa)//
{
	low[x] = dfn[x] = ++tme;
	int to;
	for (int i = head[x]; ~i; i = e[i].next)
	{
		to = e[i].to;
		if (!dfn[to])
		{
			tarjan(to, x);//
			low[x] = min(low[x], low[to]);
			if (dfn[x] < low[to])
				e[i].flag = e[i ^ 1].flag = true;
		}
		else if (to != fa)//
			low[x] = min(low[x], dfn[to]);
	}
}

(有标记注释的是不一样的地方)

输入数据

4 4

1 2
2 3
2 4
2 4

按照第二种写法,本来应该是错的

然而测试之后,发现两份代码都输出了正确答案

请问这是什么原因呢?

2023/4/2 23:06
加载中...