求证明一个东西
  • 板块学术版
  • 楼主poly
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/2/22 14:51
  • 上次更新2023/10/24 00:07:05
查看原帖
求证明一个东西
910332
poly楼主2023/2/22 14:51

有一张图,对它进行tarjan,如果扫到反向边,就记录由这条边和树边构成的环。
证明:扫到的所有环通过线性拼接,能够得到任意图中的环。

线性拼接可以理解为边集的相加减。

2023/2/22 14:51
加载中...