双联通+强联通分量题单

在写题过程中可能会不定时更新题单（简介中带有日期的题目为新添题目）。

强连通分量

强联通分量是图的连通性中的一个重要分支。对于有向图 G(V,E)。如果图中的任意两个节点 u,v 之间可以互相到达，则称这张图是强连通图。

一张有向图中的最大强联通子图为这张图的强连通分量。通常可以用 tarjan 算法求解。时间复杂度 O(n+m)，简称 SCC。

求强联通分量：

把一个强连通分量看成一个点，建立一张新图，这个过程称之为缩点。

缩点后统计度数：

缩点后统计点权：

一张有向图缩点后必然保证其实一个 DAG，搭配拓扑排序可以解决复杂问题。

缩点后拓扑排序：

在一张无向图中，若删去一条边，图的连通数增加，则称该点为割边。

如果一个无向连通图不具备割边，则称该图为边双连通图。一张无向图的最大联通边双连通图成为该图的边双联通分量，简称 e-DCC。

边双联通分量缩点后一定得到一棵树。

割边和边双联通分量：

在一张无向图中，若删去一个点，图的连通数增加，则称该点为割点。

如果一个无向连通图不具备割点，则称该图为点双连通图。一张无向图的最大联通点双连通图成为该图的点双联通分量，简称 v-DCC。

点双联通分量缩点后一定得到一棵树。

割点和点双联通分量：

给定 n 个变量，每种变量仅有两个可能的取值。再给定 m 个条件，每个条件均是对变量的限制。求是否存在 n 个变量的合法赋值，使 m 个条件均满足。

上述问题便是 2-SAT 问题。经典做法是 SCC 缩点。