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
按照第二种写法,本来应该是错的
然而测试之后,发现两份代码都输出了正确答案
请问这是什么原因呢?