Tarjan
首先是概念：
极大强连通分量：
不能再加入一点保持整个图强连通的图
强连通分量：
从任意一点能到达另一任意一点的图
Tarjan原理
-
树边 ：在树上 （图中黑色边）
-
横插边 ：从一棵子树到另一棵子树的边（图中绿色边）
3、 返祖边 ：连到自己的祖先的边
观察图，我们可以注意到：
横插边不可能构成新的强连通分量
原因：若要构成强连通分量，左侧子树必定有连向右侧子树的边，在访问左子树时便会将 强连通分量 搜出，不会产生新的，所以在遍历时 无视 横插边即可
同时，对于一个强连通分量而言，
树中一定有一个结点是强连通分量中深度最浅的结点
如图，如果一个点能成为 强连通分量 中深度最浅的结点，一定不能有返祖边跨越过该点。
所以对于右子树中的强连通分量， 绿色星星 所在的位置就是它强连通分量中深度最浅的结点
重点！！！！
对于每个点，我们记录一个 dfn[x] 为当前结点 x 的 dfs 序，再记录一个 low[x] 为 当前结点向下搜索后仅向上一次，能到达的 dfn 值最小的结点
为什么呢？
其实在强连通分量中这样搜索是没有问题的
但是在割点/割边中，这样做会 寄
（下面会讲
image844×536 98.2 KB
image666×577 10.9 KB
此处图片来自dalao @hyf
可以代入理解一下
PS：单个点也是强连通分量
Tarjan代码实现
void tarjan(int x){
dfn[x]=low[x]=++top;
vis[x]=1;//是否在栈里 为1是在栈内
q.push(x);
for(int i=head[x];i!=-1;i=a[i].next){
if(!dfn[a[i].to]){
tarjan(a[i].to);
low[x]=min(low[x],low[a[i].to]);
}else if(vis[a[i].to]&&dfn[a[i].to]<low[x]){//避免先前已经搜过部分
low[x]=dfn[a[i].to];
}
}
if(dfn[x]==low[x]){
cnt++;
while(q.top()!=x){
vis[q.top()]=0;
b[q.top()]=cnt;
q.pop();
}
vis[x]=0;
b[x]=cnt;
q.pop();
}
}
一个奇怪的算法
image915×370 23.1 KB
↑ 一个死掉的算法
原因：复杂度不比Tarjan优，被Tarjan全部代替
坦白的说：这个不用会。
image788×314 53.2 KB
定义
割点
删去这个点后无向图被分成多个部分
割边
删去这条边后无向图被分成多个部分
关于割点
图像
如图，这是一个割点的图例
回到 上面 说过的，割点在跳返祖边时不能跳过多个返祖边
就像右图中，如果跳过多个返祖边，会从割点上跳过
而有返祖边的点也可以是割点
如果连跳 割点将无法通过
dfn[x]==low[x] && 有一个孩子
具体判断割点
image698×154 27.4 KB
如果 Low[v] > dfn[u] （其中v是孩子结点，u是割点）
则割点被删去后图仍然能连通
所以必须有 Low[v]<=dfn[u] 时
割点 u 才成立
关于割边
一条没有被返祖边跨越的边即为割边
非常的简单（
2-SAT
定义
- 首先是 SAT 问题
- SAT 是指同时满足多组条件的问题
- 解法：暴力
- 因为SAT问题已经被证明为了 NPC（NP完全） 问题，只能暴力做
- 复杂度： 仅仅 O（nk）
- 2-sat 是指每个同学仅提出两个条件的问题
- 做法：建图连边，使用强连通分量
- 复杂度：大概是 O(N+M)
例子
带入到具体的例子
假设有 A,B,C 三个同学，提出了一些对于甲、乙、丙的约束
| A | 甲和乙性别相同 | 甲和丙性别不同 |
|---|---|---|
| B | 乙不能是男的 | 丙和乙性别不同 |
| C | 丙不能是女的 | 丙和甲性别不同 |
image828×586 9.19 KB
→ 男
→ 女
在赋值时，将所在的强连通分量的拓扑序较大的X赋值为1
而拓扑序较小的赋值为0
关于方形图
image704×518 47.7 KB
建图方法：
- 找到割点 x
- 新建一个方点 m
- 连接 x和m ，边权为 0
- 将 m 和连通分量里面的点连边，边权为从割点到该点的最短路
- 在方点处统计答案