双联通+强联通分量题单

在写题过程中可能会不定时更新题单（简介中带有日期的题目为新添题目）。 # 强连通分量 强联通分量是图的连通性中的一个重要分支。对于有向图 $G(V,E)$。如果图中的任意两个节点 $u,v$ 之间可以互相到达，则称这张图是**强连通图**。 一张有向图中的**最大强联通子图**为这张图的**强连通分量**。通常可以用 tarjan 算法求解。时间复杂度 $O(n+m)$，简称 SCC。 求强联通分量： - [B3609 [图论与代数结构 701] 强连通分量](https://www.luogu.com.cn/problem/B3609) 模板题 把一个强连通分量看成一个点，建立一张新图，这个过程称之为**缩点**。 缩点后统计度数： - [P2835 刻录光盘](https://www.luogu.com.cn/problem/P2835) - [P2746 [USACO5.3] 校园网Network of Schools](https://www.luogu.com.cn/problem/P2746) - [P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G](https://www.luogu.com.cn/problem/P2341) - [CF1777E Edge Reverse](https://www.luogu.com.cn/problem/CF1777E) 二分加缩点（2024.8.8） - [P4819 [中山市选] 杀人游戏](https://www.luogu.com.cn/problem/P4819) 缩点后统计点权： - [P1262 间谍网络](https://www.luogu.com.cn/problem/P1262) 一张有向图缩点后必然保证其实一个 DAG，搭配拓扑排序可以解决复杂问题。 缩点后拓扑排序： - [P3387 【模板】缩点](https://www.luogu.com.cn/problem/P3387) 模板题 - [P4742 [Wind Festival] Running In The Sky](https://www.luogu.com.cn/problem/P4742) - [P3119 [USACO15JAN] Grass Cownoisseur G](https://www.luogu.com.cn/problem/P3119) 可以用拓扑，不过 SPFA 也能过 - [P2272 [ZJOI2007] 最大半连通子图](https://www.luogu.com.cn/problem/P2272) - [P3436 [POI2006] PRO-Professor Szu](https://www.luogu.com.cn/problem/P3436)（2024.8.8） # 双连通分量 在一张无向图中，若删去一条边，图的连通数增加，则称该点为**割边**。 如果一个**无向连通图**不具备割边，则称该图为**边双连通图**。一张无向图的**最大**联通边双连通图成为该图的**边双联通分量**，简称 e-DCC。 边双联通分量缩点后一定得到一棵树。 割边和边双联通分量： - T103481 【模板】割边（非主题库内题目，简单参考即可） - [P8436 【模板】边双连通分量](https://www.luogu.com.cn/problem/P8436) 边双模板 - [P2860 [USACO06JAN] Redundant Paths G](https://www.luogu.com.cn/problem/P2860) 边双缩点后统计度数 - [P8867 [NOIP2022] 建造军营](https://www.luogu.com.cn/problem/P8867) 缩点后树上 dp 在一张无向图中，若删去一个点，图的连通数增加，则称该点为**割点**。 如果一个**无向连通图**不具备割点，则称该图为**点双连通图**。一张无向图的**最大**联通点双连通图成为该图的**点双联通分量**，简称 v-DCC。 点双联通分量缩点后一定得到一棵树。 割点和点双联通分量： - [P3388 【模板】割点（割顶）](https://www.luogu.com.cn/problem/P3388) 割点模板 - [P3469 [POI2008] BLO-Blockade](https://www.luogu.com.cn/problem/P3469) 割点简单计数 - [P8435 【模板】点双连通分量](https://www.luogu.com.cn/problem/P8435) 点双模板 - [P5058 [ZJOI2004] 嗅探器](https://www.luogu.com.cn/problem/P5058) 点双缩点（割点也能做） - [P3225 [HNOI2012] 矿场搭建](https://www.luogu.com.cn/problem/P3225) 小清新思维题 - [SP2878 KNIGHTS - Knights of the Round Table](https://www.luogu.com.cn/problem/SP2878) - [P4082 [USACO17DEC] Push a Box P](https://www.luogu.com.cn/problem/P4082)（2025.2.6） - [P7924「EVOI-RD2」旅行家](https://www.luogu.com.cn/problem/P7924) 点双性质+差分（2024.8.24） - [P4630 [APIO2018] 铁人两项](https://www.luogu.com.cn/problem/P4630) ## 2-SAT 给定 $n$ 个变量，每种变量仅有两个可能的取值。再给定 $m$ 个条件，每个条件均是对变量的限制。求是否存在 $n$ 个变量的合法赋值，使 $m$ 个条件均满足。 上述问题便是 2-SAT 问题。经典做法是 SCC 缩点。 - [P4782 【模板】2-SAT](https://www.luogu.com.cn/problem/P4782) 模板 - [P3209 [HNOI2010] 平面图判定](https://www.luogu.com.cn/problem/P3209)