强连通分量

基础概念

强连通：在有向图 $G$ 中，如果两个点 $u$ 和 $v$ 是互相可达的，即从 $u$ 出发可以到达 $v$ , 从 $v$ 也可以到达 $u$ , 则称 $u$ 和 $v$ 是强连通的。如果 $G$ 中任意两个点都是互相可达的，则称 $G$ 是强连通图。

强连通分量：如果一个有向图 $G$ 不是强连通图，那么可以把它分成多个子图， 其中每个子图的内部是强连通的, 而且这些子图已经扩展到最大，不能与子图外的任意点强连通， 称这样的一个 “极大强连通” 子图是 $G$ 的一个强连通分量。

DFS生成树

SCC(强连通分量) 中的 tarjan 算法主要是靠 DFS生成树 实现的, 所以接下来介绍DFS生成树：

有向图的 DFS 生成树主要有 4 种边：

1. 树边 ：示意图中以黑色边表示，每次搜索找到一个还没有访问过的结点的时候就形成了一条树边。
2. 反祖边 ：示意图中以红色边表示（即 7 → 1），也被叫做回边，即指向祖先结点的边。
3. 横叉边 ：示意图中以蓝色边表示（即 9 → 7），它主要是在搜索的时候遇到了一个已经访问过的结点，但是这个结点 并不是 当前结点的祖先。
4. 前向边 ：示意图中以绿色边表示（即 3 → 6），它是在搜索的时候遇到子树中的结点的时候形成的。

接下来我们考虑 DFS 生成树与强连通分量之间的关系。

如果结点 $u$ 是某个强连通分量在搜索树中遇到的第一个结点，那么这个强连通分量的其余结点肯定是在搜索树中以 $u$ 为根的子树中。结点 $u$ 被称为这个强连通分量的根。

反证法：假设有个结点 $v$ 在该强连通分量中但是不在以 $u$ 为根的子树中，那么 $u$ 到 $v$ 的路径中肯定有一条离开子树的边。但是这样的边只可能是横叉边或者反祖边，然而这两条边都要求指向的结点已经被访问过了，这就和 $v$ 不在以 $u$ 为根的子树中矛盾了。得证。

为什么这两种边都要求“指向的结点已经被访问过了”？

• 反祖边：

  • 定义：指向祖先结点的边。
  • 为什么要求已访问？ 祖先节点的定义就是在DFS过程中比当前节点更早被访问的节点。你要指回你的祖先，那个祖先肯定在你之前就被发现了。所以，当DFS走到当前节点，准备沿着反祖边走去时，它指向的那个祖先节点肯定已经被访问过了。

• 横叉边：

  • 定义：指向一个既不是祖先也不是后代，但已经被访问过的节点的边。
  • 为什么要求已访问？ 这是横叉边的核心定义！横叉边连接的是DFS树中两个不存在祖先-后代关系的分支。当你从一个分支走到另一个分支时，另一个分支的节点必然是在之前某次DFS过程中已经被探索过的。如果那个节点还没被访问，DFS就会把它作为当前节点的“后代”（形成一条树边），而不是一条横叉边。

tarjan相关概念

dfn[u]: 时间戳，DFS遍历时结点 $u$ 被搜索的次序。
low[u]: $u$ 和 $u$ 的子树里返祖边和横插边能连到还没出栈的 $dfn$ 最小的点。

按照DFS遍历次序对图中所有的结点进行搜索，维护每个结点的 $dfn$与 $low$ 变量，且让搜索到的结点入栈。每当找到一个强连通元素，就按照该元素包含结点数目让栈中元素出栈。在搜索过程中，对于结点 u 和与其相邻的结点 v（v 不是 u 的父节点）考虑 3 种情况：

1. $v$ 未被访问：继续对 $v$ 进行深度搜索。在回溯过程中，用 $lo{w}_v$ 更新 $lo{w}_u$ 。因为存在从 $u$ 到 $v$ 的直接路径，所以 $v$ 能够回溯到的已经在栈中的结点，$u$ 也一定能够回溯到。
2. $v$ 被访问过，已经在栈中：根据 low 值的定义，用 $df{n}_v$ 更新 $lo{w}_u$。
3. $v$ 被访问过，已不在栈中：说明 $v$ 已搜索完毕，其所在连通分量已被处理，所以不用对其做操作。

对于一个连通分量图，我们很容易想到，在该连通图中有且仅有一个 $u$ 使得 ${\text{dfn}}_u={\text{low}}_u$ 。该结点一定是在深度遍历的过程中，该连通分量中第一个被访问过的结点，因为它的 $dfn$ 和 $low$ 值最小，不会被该连通分量中的其他结点所影响。

因此，在回溯的过程中，判定 ${\text{dfn}}_u={\text{low}}_u$ 是否成立，如果成立，则栈中 $u$ 及其上方的结点构成一个 SCC。

void tarjan(int u) {dfn[u] = low[u] = ++tim;stk.push_back(u), in_stk[u] = true;for (auto y : e[u]) {if (dfn[y] == -1) {tarjan(y);low[u] = std::min(low[u], low[y]);} else if (in_stk[y]) {low[u] = std::min(low[u], dfn[y]);}}if (low[u] == dfn[u]) {++scc_cnt;int y;do {y = stk.back();stk.pop_back();in_stk[y] = false;id[y] = scc_cnt;siz[scc_cnt]++;}while(y != u);}}

缩点之后，我们的图就变成了一个DAG(有向无环图)，我们就可以利用有向无环图来做很多的事情，比如拓扑排序、DP等。

Template

struct SCC {int n, tim, scc_cnt;std::vector<std::vector<int>> e; std::vector<int> stk;std::vector<int> dfn, low, id;//各个点的时间戳dfn, 各个点能走到的最小的时间戳low, 对应的强连通分量id值std::vector<bool> in_stk;std::vector<int> siz;SCC() {}SCC(int _n) {init(_n);}void init(int _n) {n = _n;e.assign(n, {});dfn.assign(n, -1);in_stk.assign(n, false);low.resize(n);id.assign(n, -1);stk.clear();siz.assign(n, 0);tim = scc_cnt = 0;}void addEdge(int u, int v) { e[u].push_back(v);}void tarjan(int u) {dfn[u] = low[u] = ++tim;stk.push_back(u), in_stk[u] = true;for (auto y : e[u]) {if (dfn[y] == -1) {tarjan(y);low[u] = std::min(low[u], low[y]);} else if (in_stk[y]) {low[u] = std::min(low[u], dfn[y]);}}if (low[u] == dfn[u]) {++scc_cnt;int y;do {y = stk.back();stk.pop_back();in_stk[y] = false;id[y] = scc_cnt;siz[scc_cnt]++;}while(y != u);}}std::vector<int> work() {for (int i = 1;i <= n; i++) {if (dfn[i] == -1) {tarjan(i);}}return id;}};

2-SAT

背景

假设有 $n$ 对夫妻被邀请参加一个聚会，每对夫妻中只有一人可以列席。在 $2\times n$ 个人中，某些人（不包括夫妻）之间有着很大的矛盾，有矛盾的两个人不会同时出现在聚会上，有没有可能让 $n$ 个人同时列席 ？

现在让我们思考这个问题，如果我们没有学过相关算法，我们大概会这样做：每对夫妻都枚举一个人然后一个一个试，时间复杂度高达 $O\left(2^n\right)$ 。

定义

2-SAT，简单的说就是给出 $n$ 个集合，每个集合有两个元素，已知若干个 $⟨a,b⟩$ ，表示 $a$ 与 $b$ 矛盾（其中 $a$ 与 $b$ 属于不同的集合）。然后从每个集合选择一个元素，判断能否一共选 $n$ 个两两不矛盾的元素。显然可能有多种选择方案，一般题中只需要求出一种即可。

解决方法

针对2-SAT问题，我们可以选择使用SCC + 拓扑排序来解决。

第一步，我们要开始建图：
我们利用矛盾关系来建图，比如 $A$ 和 $B$ 矛盾，$\overline{A}$ 和 $\overline{B}$ 矛盾，这就意味着 $A$ 出现的时候， $\overline{B}$ 就一定要出现， 同理，$B$ 出现的时候 $\overline{A}$ 也一定要出现, 这个时候我们就可以用 $A$ 指向 $\overline{B}$ , 然后 $B$ 指向 $\overline{A}$ 。

第二步，我们应该如何判断是否有解呢 ？
当我们建成一个有向图之后，根据SCC的定义，每个SCC里面各个点都是相互依赖的（一个点出现，其他点都要出现），如果一个人和他的对立面（比如 $A$ 和 $\overline{A}$ ）同时出现在一个SCC，则证明无解。

第三步，证明有解之后我们该怎么办呢？
我们先缩点，缩完点之后整张图就变成了一张DAG, 然后我们思考，我们建图时指向的就是被依赖的，那么我们肯定就是优先选择被依赖的更多的，那么其实就是一个逆向的拓扑排序, 不过实际上我们并不需要真正的做拓扑排序，因为SCC编号就是逆向的拓扑排序，SCC编号越小，出现优先级越高。

时间复杂度为 $O(n+m)$ 。

例题

基础思路

假设 $x$ 为 0， $y$ 为 1 为 一个条件，那么 $x$ 为 1 时，$y$ 就必然需要为 1，$y$ 为 0 时，$x$ 就必然需要为 0，依赖关系已经形成。

代码模板

#include <bits/stdc++.h>using ll = long long;#ifndef DEBUG
#define debug(x)
#endifstruct TwoSat {int n;std::vector<std::vector<int>> e;std::vector<bool> ans;TwoSat() {}TwoSat(int _n) {init(_n);}void init(int _n) {n = _n;e.resize(2 * n);ans.resize(n);}void addEdge(int u, int a, int v, int b) {int na = (a ^ 1), nb = (b ^ 1);e[u + na * n].push_back(v + b * n);e[v + nb * n].push_back(u + a * n); }bool satisfiable() {std::vector<int> id(2 * n, -1), dfn(2 * n, -1), low(2 * n, -1);std::vector<int> stk;std::vector<bool> in_stk(2 * n, false);int tim = 0, scc_cnt = 0;std::function<void(int)> tarjan = [&](int u) {dfn[u] = low[u] = ++tim;stk.push_back(u), in_stk[u] = true;for (auto v: e[u]) {if (dfn[v] == -1) {tarjan(v);low[u] = std::min(low[u], low[v]);} else if (in_stk[v]) {low[u] = std::min(low[u], dfn[v]);}}if (dfn[u] == low[u]) {scc_cnt++;int y;do {y = stk.back();stk.pop_back();in_stk[y] = false;id[y] = scc_cnt;} while (y != u);}}; for (int i = 0;i < 2 * n; i++) {if (dfn[i] == -1) {tarjan(i);}}for (int i = 0;i < n;i++) {if (id[i] == id[i + n]) {return false;}ans[i] = id[i] > id[i + n];}return true;}std::vector<bool> answer() {return ans;}
};int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int n, m;std::cin >> n >> m;TwoSat g(n);for (int i = 1;i <= m; i++) {int x, a, y, b;std::cin >> x >> a >> y >> b;x--;y--;g.addEdge(x, a, y, b);} if (g.satisfiable()) {std::vector<bool> ans = g.answer();std::cout << "POSSIBLE\n";for (int i = 0;i < n; i++) {if (ans[i]) {std::cout << 1 << " ";} else {std::cout << 0 << " ";}}} else {std::cout << "IMPOSSIBLE\n";}return 0;
}

差分约束

差分约束系统 是一种特殊的 $n$ 元一次不等式组，它包含 $n$ 个变量 $x_1,x_2,\dots ,x_n$ 以及 $m$ 个约束条件，每个约束条件是由两个其中的变量做差构成的，形如 $x_i-x_j\le c_k$，其中 $1\le i,j\le n,i\ne j,1\le k\le m$ 并且 $c_k$ 是常数（可以是非负数，也可以是负数）。我们要解决的问题是：求一组解 $x_1=a_1,x_2=a_2,\dots ,x_n=a_n$，使得所有的约束条件得到满足，否则判断出无解。

差分约束系统中的每个约束条件 $x_i-x_j\le c_k$ 都可以变形成 $x_i\le x_j+c_k$，这与单源最短路中的三角形不等式 $dist[y]\le dist[x]+z$ 非常相似。因此，我们可以把每个变量 $x_i$ 看做图中的一个结点，对于每个约束条件 $x_i-x_j\le c_k$，从结点 $j$ 向结点 $i$ 连一条长度为 $c_k$ 的有向边。

注意到，如果 {a1,a2,…,an}\{a_1,a_2,\dots,a_n\}{a1​,a2​,…,an​} 是该差分约束系统的一组解，那么对于任意的常数 $d$，{a1+d,a2+d,…,an+d}\{a_1+d,a_2+d,\dots,a_n+d\}{a1​+d,a2​+d,…,an​+d} 显然也是该差分约束系统的一组解，因为这样做差后 $d$ 刚好被消掉。

算法流程

设 $dist[0]=0$ 并向每一个点连一条权重为 $0$ 的边，跑单源最短路，若图中存在负环，则给定的差分约束系统无解，否则，$x_i=dist[i]$ 为该差分约束系统的一组解。

例题

#include <bits/stdc++.h>using ll = long long;#ifndef DEBUG
#define debug(x)
#endifconstexpr int inf = 2e9;int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int n, m;std::cin >> n >> m;std::vector<std::vector<std::pair<int, int>>> adj(n + 1);for (int i = 0;i < m; i++) {int u, v, c;std::cin >> u >> v >> c;adj[v].push_back({u, c});}for (int i = 1;i <= n; i++) {adj[0].push_back({i, 0});}std::queue<int> q;std::vector<int> cnt(n + 1, 0), w(n + 1, inf);std::vector<bool> st(n + 1, false);q.push(0);w[0] = 0;while (!q.empty()) {auto u = q.front();q.pop();st[u] = false;for (auto [v, c]: adj[u]) {if (w[v] > w[u] + c) {w[v] = w[u] + c;if (!st[v]) {q.push(v);cnt[v]++;if (cnt[v] > n) {std::cout << "NO\n";return 0;}st[v] = true;}}}}for (int i = 1;i <= n; i++) {std::cout << w[i] << " ";}return 0;
}