强连通分量 & 缩点

都是强连通分量的基础,AK 这个题单应该就能说自己还是会一点强连通分量的。

应该会持续更新

基础题:

P2863 The Cow Prom S 统计强连通分量个数

B3609 强连通分量 求出所有强连通分量

P1407 稳定婚姻 判断两点是否在同一强连通分量

缩点后统计度数:

P2341 受欢迎的牛 G

P2002 消息扩散

P2835 刻录光盘

P2746 校园网 Network of Schools

P7251 强连通图

P4819 杀人游戏 需要去重边

关于点权:

P2194 HXY烧情侣 求缩点后点权和

CF427C Checkposts

P1262 间谍网络

缩点后拓扑:

P3387 【模板】缩点

P1073 最优贸易

P3627 抢掠计划

P4306 连通数

CF467D Fedor and Essay 有两种点权,稍麻烦

P3436 PRO-Professor Szu 注意细节

CF1900E Transitive Graph

杂:

P1455 搭配购买 缩点后 01 背包(似乎并查集也行?)

P2169 正则表达式 缩点后跑最短路


  1. P2863 - [USACO06JAN] The Cow Prom S
  2. B3609 - [图论与代数结构 701] 强连通分量
  3. P1407 - [国家集训队] 稳定婚姻
  4. P2341 - [USACO03FALL / HAOI2006] 受欢迎的牛 G
  5. P2002 - 消息扩散
  6. P2835 - 刻录光盘
  7. P2746 - [IOI 1996 / USACO5.3] 校园网 Network of Schools
  8. P7251 - [JSOI2014] 强连通图
  9. P4819 - [中山市选] 杀人游戏
  10. P2194 - HXY烧情侣
  11. CF427C - Checkposts
  12. P1262 - [POI 1996 R3] 间谍网络
  13. P3387 - 【模板】缩点
  14. P1073 - [NOIP 2009 提高组] 最优贸易
  15. P3627 - [APIO2009] 抢掠计划
  16. P4306 - [JSOI2010] 连通数
  17. CF467D - Fedor and Essay
  18. P1455 - 搭配购买
  19. P2169 - 正则表达式
  20. P3436 - [POI 2006] PRO-Professor Szu
  21. CF1900E - Transitive Graph
  22. P2656 - 采蘑菇