rt,本题难度不大,但是楼主比较手残,写了 3 发才过,下面是一些可能的常见错误。
- 44pts:割点的编号使用空格隔开,而非换行。
- 36pts:
Tarjan(i) 要运行多次,因为图不一定联通,但是注意判断是否允许的条件为 if (!dfn[i])。
- 12pts:注意到了图不一定联通,但是
Tarjan(i) 中理解错误了。
Tarjan(x) 中最后特判的不是割点的条件是 if (x != R && cnt < 2),不是 if (x != 1 && cnt < 2)。
此处的 R 的确定在主函数中调用时确定,也就是在写 if (!dfn[i]) 时,其内容为 R = i, Tarjan(i);。特别注意,R 要开全局。
如果出现了其他的分数,有可能是出现了其中的多个问题,也有可能就是单纯写挂了。