Tarjan
首先是概念:
极大强连通分量:
不能再加入一点保持整个图强连通的图
强连通分量:
从任意一点能到达另一任意一点的图
Tarjan原理
-
树边 :在树上 (图中黑色边)
-
横插边 :从一棵子树到另一棵子树的边(图中绿色边)
3、 返祖边 :连到自己的祖先的边
观察图,我们可以注意到:
横插边不可能构成新的强连通分量
原因:若要构成强连通分量,左侧子树必定有连向右侧子树的边,在访问左子树时便会将 强连通分量 搜出,不会产生新的,所以在遍历时 无视 横插边即可
同时,对于一个强连通分量而言,
树中一定有一个结点是强连通分量中深度最浅的结点
如图,如果一个点能成为 强连通分量 中深度最浅的结点,一定不能有返祖边跨越过该点。
所以对于右子树中的强连通分量, 绿色星星 所在的位置就是它强连通分量中深度最浅的结点
重点!!!!
对于每个点,我们记录一个 dfn[x] 为当前结点 x 的 dfs 序,再记录一个 low[x] 为 当前结点向下搜索后仅向上一次,能到达的 dfn 值最小的结点
为什么呢?
其实在强连通分量中这样搜索是没有问题的
但是在割点/割边中,这样做会 寄
(下面会讲
此处图片来自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();
}
}
一个奇怪的算法
↑ 一个死掉的算法
原因:复杂度不比Tarjan优,被Tarjan全部代替
坦白的说:这个不用会。
定义
割点
删去这个点后无向图被分成多个部分
割边
删去这条边后无向图被分成多个部分
关于割点
图像
如图,这是一个割点的图例
回到 上面 说过的,割点在跳返祖边时不能跳过多个返祖边
就像右图中,如果跳过多个返祖边,会从割点上跳过
而有返祖边的点也可以是割点
如果连跳 割点将无法通过
dfn[x]==low[x]\ \&\& \ 有一个孩子
具体判断割点
如果 Low[v] > dfn[u] (其中v是孩子结点,u是割点)
则割点被删去后图仍然能连通
所以必须有 Low[v] <= dfn[u] 时
割点 u 才成立
关于割边
一条没有被返祖边跨越的边即为割边
非常的简单(
2-SAT
定义
- 首先是 SAT 问题
- SAT 是指同时满足多组条件的问题
- 解法:暴力
- 因为SAT问题已经被证明为了 NPC(NP完全) 问题,只能暴力做
- 复杂度: 仅仅 O(n^k)
- 2-sat 是指每个同学仅提出两个条件的问题
- 做法:建图连边,使用强连通分量
- 复杂度:大概是 O(N+M)
例子
带入到具体的例子
假设有 A,B,C 三个同学,提出了一些对于甲、乙、丙的约束
A | 甲和乙性别相同 | 甲和丙性别不同 |
---|---|---|
B | 乙不能是男的 | 丙和乙性别不同 |
C | 丙不能是女的 | 丙和甲性别不同 |
\to 男
\to 女
在赋值时,将所在的强连通分量的拓扑序较大的X赋值为1
而拓扑序较小的赋值为0
关于方形图
建图方法:
- 找到割点 x
- 新建一个方点 m
- 连接 x和m ,边权为 0
- 将 m 和连通分量里面的点连边,边权为从割点到该点的最短路
- 在方点处统计答案