二分图 & SCC 学习笔记 (7.3~7.8)
1. 基础概念
二分图：指一无向图，使得存在两个集合，使得两个集合内任意二点不存在连边。
注：树一定是二分图。
匹配：由一组没有公共端点的不是环的边构成的集合。其中任意两条边没有共同节点。
最大匹配：在图中使得总边数最大的匹配。
增广路：若在一条路径中，某匹配集合中的边与不在匹配集合中的边交替出现，则称该路径为增广路径。
注：两端连边均为未匹配边。
强连通：在有向图\(V\)中任意两个节点存在路径连通。
强连通分量：在图\(G\)中的极大（指加入图G中其他任意一条边都会使其不再强联通）强联通子图。
2.算法思路
匈牙利（增广路）算法：
解决二分图最大匹配问题。
核心为不断地寻找增广路来扩充匹配集合。
因为增广路中未匹配边 = 匹配边 + 1
所以可将增广路中未匹配边匹配，最大匹配 + 1.
伪代码：
while found u[i]->v[j]:
if !(v[i] ∈ M):#M为增广路径集合
push(v[i]) -> M
if v[i]未覆盖 || v[i]的原覆盖点能找到增广路:
v[i]覆盖点 = u[i]
return True
return False
\(Code\):
int n, m, q;
int road[maxm], mk[maxm];
vector <int> g[maxn];
bool find(int x){
for(int i = 0; i < g[x].size(); i++){
if(mk[i] < dfn){
if(!road[i] || find(road[i])){
road[i] = x;
return 1;
}
}
}
return 0;
}
int main(){
cin >> n >> m >> q;
for(int i = 1; i <= q; i++){
int x, y;
cin >> x >> y;
g[x].push_back(y);
}
for(int i = 1; i <= m; i++)
dfn++, ans += find(i);
return 0;
}
2. Tarjan算法
找到图中的所有强联通分量。
前置芝士：DFS生成树
Tarjan算法中为每个节点 \(u\) 维护了以下数组：
\(dfn_u\)：深度优先搜索遍历\(DFS\)搜索树时节点 \(u\) 被遍历的次序，即点 \(u\) 在树中的编号。
\(low_u\)：在 \(u\) 的子树中通过返祖边能狗够回溯到的最早且在栈中的节点。
令 \(Subtree_u\) 为以 \(u\) 为根的子树。
\(low_u\) 定义为 \(Subtree_u\) 的节点或由 \(Subtree_u\) 的返祖边能到达的节点的 \(dfn\) 的最小值。
按照节点的 \(dfs\) 序对图中所有的节点进行搜索，并维护节点的 \(low,dfn\) 值。
让当前被搜索到的节点入栈。
每找到一个强联通元素，便让栈中所有属于该元素的节点出栈。
在搜索过程中，对于二节点 \((u,v)\)，满足 \(v.fath≠u\) 考虑：
- \(v\) 未被搜索到：\(dfs(v)\)，在回溯过程中，用 \(low_v\) 更新 \(low_u\)。
- \(v\) 被搜索到，但不在栈中：\(v\) 已搜索完毕，其 $ SCC$ 已被处理，不用操作。
- \(v\) 被搜索到，在栈中：用\(dfn_v\) 更新 \(low_u\)。
搜索结束后，若有 \(dfn_u=low_u\) ，则依次弹出栈内元素，并做处理。（栈中 \(u\) 及其上方的节点构成一个 \(SCC\)）
伪代码：
func tarjan(int u):
mk[u] = True, low[u] = dfn[u] = ++dfnCnt
push(u) -> stack
for found (u, v):
if !mk[u]:
tarjan(v)
low[u] = min(low[u], low[v])
elif inStack[v] == True:
low[u] = min(low[u], dfn[v])
if dfn[u] == low[u]:
sc++
while True:
scc[stack.top] = sc
size[sc]++
instack[stack.top] = False
stack.pop
if(stack.top == u)break
\(Code:\)
int n;
int dfn[maxm], low[maxm], inStack[maxm], scc[maxm], Size[maxm], res[maxm], s[maxm];
int mk[maxm];
int dfncnt, sc, v, ans, top;
vector <int> g[maxm];
void tarjan(int u){
low[u] = dfn[u] = dfncnt;
s[++top] = u;
inStack[u] = 1;
for(int i = 0; i < g[u].size(); i++){
int v = g[u][i];
if(!dfn[v])tarjan(v), low[u] = min(low[u], low[v]);
else if(inStack[v])low[u] = min(low[u], dfn[v]);
}
if(dfn[u] == low[u]){
sc++;
while(s[top] != u)scc[s[top]] = sc, Size[sc]++, inStack[s[top]]=0, top--;
scc[s[top]] = sc, Size[sc]++, inStack[s[top]]=0, top--;
}
}
int main(){
input();
for(int i = 1;i <= n;i++)
if(!dfn[i])tarjan(i);
}