警示后人/如果你样例不过/wa on test 8/12
查看原帖
警示后人/如果你样例不过/wa on test 8/12
912241
dream_on_screen楼主2025/1/8 22:00
  1. 在使用 tarjan 缩点的时候需要注意可能会有重边。这里不能忽略重边,因为如果有重边的话那么这两个点就在一个边双连通分量里了

hack:见样例2

  1. 在倍增求 lca 预处理之前要确定所需的信息有没有都被求出来了

hack:(测试数据#8)

in:
8 7 8
6 3
4 5
2 5
7 3
7 8
4 7
1 5
6 3
5 2
6 3
6 4
6 3
6 3
1 5
5 2
expect:
Yes
  1. 原图没有保证是联通的,所以缩点后可能是森林,不一定是一棵树

hack:

in:
4 2 1
1 2
3 4
2 4
expect:
No
2025/1/8 22:00
加载中...