SCC
二分图 & SCC 学习笔记 (7.3~7.8)
二分图 & SCC 学习笔记 (7.3~7.8) 1. 基础概念 二分图：指一无向图，使得存在两个集合，使得两个集合内任意二点不存在连边。 注：树一定是二分图。 匹配：由一组没有公共端点的不是环的边构成的集合。其中任意两条边没有共同节点。 最大匹配：在图中使得总边数最大的匹配。 增广路：若在一条路径 ......
【dp】【竞赛图的性质】ARC163D Sum of SCC 题解
ARC163D 发现这个竞赛图一定能被分为两个集合 \(A\)，\(B\)。满足 \(\forall u\in A,v\in B\)，均有 \(u\to v\in E\)。答案就是划分这两个集合的方案数。 证明： 首先，竞赛图缩完点后一定是一条链，对强连通分量进行标号，满足编号小的强连通分量指向编号 ......
强连通分量 SCC
在有向图中，如果点 \(u\) 和点 \(v\) 可以互相到达，我们就可以称 \(u,v\) 是强联通。 强联通分量就是极大的强联通子图，使得 \(u \in S,v \in S\) 都有 \(u,v\) 为强联通关系。 DFS 生成树 在介绍该算法之前，先来了解 DFS 生成树，我们以下面的有向图 ......
【竞赛图】【DP】ARC163D Sum of SCC 题解
ARC163D 发现这个竞赛图一定能被分为两个集合 \(A\)，\(B\)。满足 \(\forall u\in A,v\in B\)，均有 \(u\to v\in E\)。答案就是划分这两个集合的方案数。 证明： 首先，竞赛图缩完点后一定是一条链，对强连通分量进行标号，满足编号小的强连通分量指向编号 ......
Tarjan(scc)
`Tarjan` 算法之一是一个强连通分量算法，可以找出所有的强连通分量，时间复杂度线性。 算法中对于搜索树（如下图）作了如下定义： \in E}[u 给竞赛图每个 SCC （强连通分量）缩点后，剩下的是由一条**极长**的链与某些前向边组成的图。 于是 SCC 的数量能够转换 ......
[笔记]Tarjan算法求强联通分量（SCC）学习笔记
# [笔记]Tarjan算法求强联通分量（SCC）学习笔记 ## P1 定义 1. **dfs搜索树**：就是在搜索过程中，所构成的树状结构，并且几个节点的搜索树中不包括他的父亲。 2. **树边、横叉边、返祖边、前向边**：以下图举例子：  [AtCoder 传送门](https://atcoder.jp/contests/arc163/tasks/arc163_d "AtCoder 传送门") 怎么连这种相对传统 ......