强联通等
概念
-
极大连通分量：不能再加一个点使这个图成为一个新的连通分量
-
无向图连通分量：很明显连起来就是了
-
有向图：所有点都可以到达任意一个点，但是不一定能走回去。这就是弱联通分量。若是可以回去，那就是强联通分量。有向图联通分量的极大联通分量是强联通分量。
TARJAN！
DAG:有向无环图 如果把一个环（连通分量）缩成一个点，那么一张有向图就破坏性质地变成了DAG
在Tarjan中：
我们建成一棵dfs树，代表dfs序。我们有三种边：
- 树边 （图中黑色
- 返租边（子节点连一条边到祖先 图中红色
- 横插边（子节点连一条边到别的子节点 图中绿色
其中横插边是有向图特有的，所以我们暂时只考虑返租边。
定义两个数组 dfn：dfs序 low：下游的所有点里中返租边能爬到最高的点的那个点的编号 注意此时只能爬一次（好拗口） 结点都塞stack里面，每次更新dfn和low。
这个结点被访问过：是树边，继续dfs 没有：是返租边，更新low 根本不在栈里：横插边，不去管他
当dfn和low相等时，退栈，说明此点是这个强联通分量的一个顶点。看下面的程序应该足够明了了
一个小小的问题：为什么在返租边min(low[u],dfn[v])第二项不是low[v] 是为什么？
就结论来说：强联通分量的时候两者都是可以的，割点的时候只能是dfn。
kosarsju 老师：它被tarjan完全覆盖，所以不用会
但是我出于尊重，我还是截个图
一些小小的性质
割点和割边
一个点下面只有一个返租边：还是割点。但是有多个跨越自己的时候，就无法用dfn和low判断割点。因此在向下走之后只能跨越一条返租边。这样上面那个奇怪问题的解答。强联通分量不重视这个，所以可以填成low
割点特征（满足其一）：
- 是根并且有多个子树
- 不为树根，存在父子边使得dfn(u)<low(v) 也就是没有一条返租边越过它
割边：
更简单了。两边是割点就可以了……大概？
2-SAT
SAT问题：三组括号之间要班组三个要求，用and连接。括号里面的是or
3-SAT甚至是NPC的问题，以上的肯定也是NPC
然而2-SAT——
它不是！
使用强联通分量，将每一个变量拆成两个点
假设在强联通中每一个根是1，=婚后加密黁小太阳
所以我下想企鹅，也亏U，应该轩0放肆第一样2
这个博客很好，瞅去了
很裸的2-SAT 诶
袜！NOI原题诶！
首先除了x之外，每个地图只能用两种车，就是01两个状态，所以是2-SAT问题很正确。
只有只要枚举x的情况，再跑一个裸的2-SAT就做完了。
首先考虑如果这是一棵树的情况：我们暴力枚举中间点。这个时候这个点的两个儿子必须在左子树、右子树、父亲连上去那一坨子树中，并且不能在三个中同一个子树当中。所以对于每一个中间点，我们就把三个子树的size-1乘起来就好了
对于这道题
首先需要知道一个 *** 仙人掌图***
（一堆一堆的环堆起来的图
然后我们在每一个仙人掌图的中间建一个方点，然后我们删掉黑边留下树边和红边——我们将这个有环的无向图变成了一棵树！
然后我们需要知道两个点的距离，相当于求他们的lca。但是有时候他们的lca是一个方点，所以我们在lca最近的两条边减掉加上那条黑边就可以了。
那么我们回到题目，现在我们有很多点双连通分量。这很方便，我们用tarjan求出所有的双连通分量。这个之后一个分量上dfs序一定是连续的。但是我们需要作一些改动，每当dfn = low，直接弹栈，全部弹空，但是不能弹出自己。至此，圆方树就已经建好了。
这个时候这个s，c，f这个三元组有两种情况
- 他们属于同一个点双、
- 他们属于不同的点双
第一种情况直接c的暴力就可以完成了
第二种情况我们就枚举c，和树上做法差不多（注意必须要不同的点双，否则这一次的贡献之前已经计算过了）然后加入亿点点细节（昏倒），就可以完成第二种情况