wangbinfeng @ 2024-07-17 17:51:30
RT，这篇题解
我主要对主函数调用tarjan()提出质疑，因此在下面放两种实现调用tarjan()的代码：
for(register int i=1;i<=n;++i)
if(!dfn[i])tarjan(i,i);然而，具体tarjan()函数实现如下：
void tarjan(int x,int father){
dfn[x]=low[x]=++nowtime;
s.push(x);
for(register int i=head[x];i;i=e[i].next){
int v(e[i].to);
if(!dfn[v]){
tarjan(v,i);
low[x]=Min(low[x],low[v]);
}else if(i!=(father^1))low[x]=Min(low[x],dfn[v]);
}
if(dfn[x]==low[x]){
++dcccnt;
int k;
do{
k=s.pop();
belong[k]=dcccnt;
}while(k!=x);
}
}可以发现，tarjan()的第二个形参father表示到这个点的边，用来防止同一条边重复执行，但是主函数中调用时传的初始值为i，那么我思考是否存在一种特殊情况，即点的编号和边的编号相同，使tarjan误以为某条便已被询问而不再继续执行。
by wangbinfeng @ 2024-07-17 17:53:57
@东灯 希望能得到您的赐教，不胜感激
by 东灯 @ 2024-07-17 22:16:34
@wangbinfeng 抱歉抱歉，我已经退役好久了（捂脸），我这两天比较忙，不着急的话我后两天详细看下代码
by 东灯 @ 2024-07-17 22:18:04
顺带你的这种情况我目前应该是还没遇到过，是否能构造hack？感觉是一个和存图方式相关的问题？
by wangbinfeng @ 2024-07-17 22:48:39
@东灯 没事，就是今天正好老师讲，然后让我自己研究题解，一直没搞懂所有题解中father的意思（一般father变量表示父节点），然后通过抑或操作得知了father指边，或者换句话说，所有题解的tarjan(i,i)或tarjan(i,0)误导了我，不过其他题解精明的以2为边编号的开始，避开了这个问题
by wangbinfeng @ 2024-07-17 22:50:46
然后你的bug其实也不是我从你的代码发现的，是我们老师用他的代码讲课，被我发现了bug。我发现这个bug可以通过所有OJ的数据，然后就到luogu题解区找存在同样bug的题解，不幸的是，只有你一个人的题解中招（也许还有一个，但是他的题解我没看懂qwq）
hack数据没搞，抽空可以搞一个（太懒了），原理应该不难
by wangbinfeng @ 2024-07-17 22:51:19
@东灯 和存图方式没太大关系，主要是这个编号冲突的问题
by Po7ed @ 2024-07-17 23:14:59
也许能 hack