先简单介绍一下 dfs 生成树。

dfs 生成树在于更好地描述一个图，以往对于图问题的理解都太抽象了，无法形成对一个图的形式化描述。

有向图 dfs 树

对一个有向图进行 dfs 遍历，遍历到边 $(u,v)$ 时，若 $v$ 未被遍历过，那么保留边 $(u,v)$，令 $u$ 是 $v$ 的父节点。

那么形成一棵自祖先指向后代的有向树。

在遍历过程中，图中的边可以分成若干类：

• 树边：dfs 生成树的边
• 反祖边（回边）：指向祖先的边
• 横叉边：边的两点在 dfs 生成树中无祖先-后代关系
• 前向边：指向后代的边

无向图 dfs 树

对一个无向图进行 dfs 遍历，遍历到边 $(u,v)$ 时，若 $v$ 未被遍历过，那么保留边 $(u,v)$，令 $u$ 是 $v$ 的父节点。

保留的边形成一棵无向树。

在遍历过程中，图中的边可以分成两类：

• 树边：dfs 生成树中的边
• 非树边：连接祖先-后代的边

与有向图 dfs 生成树相比，无向图 dfs 生成树性质更强。

无向图 dfs 树没有横叉边、前向边，是因为如果边的另一端的点是已经遍历过的，那么就会成为树边。连接祖先-后代的边除外，因为 dfs 是深度优先，所以可以出现后代被遍历过。

环

容易发现，无向图环由若干条树边和非树边形成。

对于某一条非树边，其和所对应的树上的树链形成的环称为基环（笔者自己叫的），那么任意一个树上的环，都是由若干个连续基环形成的。

强连通分量

定义：

强连通：在有向图中，任意两个结点 $u,v$ 都满足 $u$ 可达 $v$ 且 $v$ 可达 $u$。

强连通分量：极大的强连通子图。

Tarjan：

dfs 整个图，递归到 $x$ 时，将 $x$ 入栈。

维护两个数组：

• $df{n}_x$ 表示 dfs 过程中首次访问到的时间戳
• $lo{w}_x$ 表示 dfs 树中 $x$ 的的子树中能够回溯到的还在栈中的最小 dfn。

当回溯到 $lo{w}_x=df{n}_x$ 时，将栈中的元素弹出，形成一个强连通分量。

点击展开代码

void dfs(int x) {
    low[x] = dfn[x] = ++idx;
    vis[x] = 1;
    q.push(x);
    for (auto u : p[x]) {
        if (!dfn[u]) {
            dfs(u);
            low[x] = min(low[x], low[u]);
        } else if (vis[u]) {
            low[x] = min(low[x], dfn[u]);
        }
    }
    if (dfn[x] == low[x]) {
        ++id;
        while (q.top() != x) {
            auto now = q.top();
            q.pop();
            vis[now] = 0;
            num[now] = id;
            scc[id].push_back(now);
        }
        q.pop();
        vis[x] = 0;
        num[x] = id;
        scc[id].push_back(x);
    }
}
// 求完 SCC 后 q 不一定为空
for (int i = 1; i <= n; i++) {
    if (!dfn[i])
        dfs(i);
}

性质：

• 一个点只属于一个 SCC。
• SCC 缩点后是 DAG。
• 一般 DAG 可以按 dfs 完成时间的逆序得到拓扑序，但不能直接使用首次访问时间 $dfn$ 的逆序。本文代码在 SCC 弹栈时递增编号；若原图存在一条跨 SCC 的边 $u\to v$，则 $nu{m}_u>nu{m}_v$。因此，SCC 编号的降序是缩点 DAG 的一个拓扑序，升序是逆拓扑序。

杂谈：

强连通分量是环套环，也就是强连通分量中的每一条边都被至少一个环经过。

强连通分量是极大强连通子图，所以要求是“最大环”，所以要求能回溯到的最小点。

$df{n}_x=lo{w}_x$ 时说明环不能再扩大了，所以形成了一个强连通分量。

边双连通分量

定义：

边双连通：两个点 $u$ 和 $v$，如果无论删去哪一条边都不能使它们不连通。

边双连通分量：极大边双连通分量。

Tarjan：

考虑这样一个结论：

• 对于任意两个有公共点或公共边的环，属于同一个边双连通分量（也就是边双连通分量的传递性）。

而，对于强连通分量，同样的，对于任意两个有公共点或公共边的环，属于同一个强连通分量。

边双连通分量和强连通分量一样是环套环，所以求边双连通分量的过程实际上就是求强连通分量的过程。

直接套用 Tarjan 求强连通分量即可。

注意一点：$x$ 不能走反边到 $f{a}_x$，一方面，这会和子树中回到到 $f{a}_x$ 的 dfn 产生混淆；另一方面，这不符合 low 在 dfs 子树中的定义。

点击展开代码

void dfs(int x, int y) {
    dfn[x] = low[x] = ++idx;
    vis[x] = 1;
    q.push(x);
    for (auto [u, id] : p[x]) {
        if ((id ^ y) == 1)
            continue;
        if (!dfn[u]) {
            dfs(u, id);
            low[x] = min(low[x], low[u]);
        } else if (vis[u]) {
            low[x] = min(low[x], dfn[u]);
        }
    }
    if (dfn[x] == low[x]) {
        id++;
        while (q.top() != x) {
            auto now = q.top();
            q.pop();
            vis[now] = 0;
            ecc[id].push_back(now);
        }
        q.pop();
        vis[x] = 0;
        ecc[id].push_back(x);
    }
}
// 求完 ECC 后 q 不一定为空
for (int i = 1; i <= n; i++) {
    if (!dfn[i])
        dfs(i, 0);
}

性质：

边双连通分量缩完图后是一棵树，树上每一个节点是一个边双，每一条边是一条桥（反之亦然：每一个边双是缩完图后一个节点，每一条桥是缩完图后的每一条边）。

点双连通分量

定义：

点双连通：对于两个点 $u$ 和 $v$，如果无论删去哪个点（只能删去一个，且不能删 $u$ 和 $v$ 自己）都不能使它们不连通。

点双连通分量：一个无向图中的极大点双连通的子图。

Tarjan：

和强连通分量、边双连通分量不同，点双连通分量不具有传递性，一个点可能会属于多个点双连通分量。

但是只有割点会属于多个点双（容易证明，如果不是割点，那么删除这个点，这个点属于的多个点双会不连通（如果不会不连通那么这多个点双又可以合并成一个点双），那么就是割点）。

点双连通分量统计时，需要在从儿子回溯时统计，不能在回溯割点的时候统计。

对于 dfs 树边 $(u,v)$，若 $lo{w}_v<df{n}_u$，则 $v$ 的子树可以绕过 $u$ 到达 $u$ 的真祖先；若 $lo{w}_v\ge df{n}_u$，则 $v$ 的子树无法绕过 $u$ 到达 $u$ 的父侧。此时将递归 $v$ 后栈中的点弹出，并加入 $u$，形成一个点双连通分量；当 $u$ 不是 dfs 树根时，$u$ 也是割点。注意 $lo{w}_v$ 可能严格处于 $df{n}_u$ 与 $df{n}_v$ 之间，不能只判断两个端点相等。

若 $x$ 是 dfs 树的根需要特判，因为此时删除 $u$ 不会有父节点使得 dfs 树变成两部分。

具体而言：

• 有两个以上子节点，那么删除 $u$ 后，子节点会相互独立（无向图没有横叉边）
• 只有一个子节点，这个点双没有割点。
• 没有子节点，这个点自身构成一个点双。

点击展开代码

// p[x] 存储 (to, eid)，同一条无向边的两个方向编号互为 eid ^ 1
// y 表示进入 x 的边编号；dfs 树根没有父边，传入 -1
void dfs(int x, int y, int root) {
    dfn[x] = low[x] = ++idx;
    if (x == root && p[x].empty()) {
        vcc[++id].push_back(x);
        return;
    }
    q.push(x);
    int son = 0;
    for (auto [u, eid] : p[x]) {
        if (y != -1 && eid == (y ^ 1))
            continue;
        if (!dfn[u]) {
            dfs(u, eid, root);
            low[x] = min(low[x], low[u]);
            if (low[u] >= dfn[x]) {
                if (x != root)
                    cut[x] = 1;
                id++;
                while (q.top() != u) {
                    auto now = q.top();
                    q.pop();
                    vcc[id].push_back(now);
                }
                q.pop();
                vcc[id].push_back(u);
                vcc[id].push_back(x);
            }
            if (x == root)
                son++;
        } else
            low[x] = min(low[x], dfn[u]);
    }
    if (son >= 2 && x == root)
        cut[x] = 1;
}
// 求完 VCC 后 q 不一定为空
for (int i = 1; i <= n; i++)
    if (!dfn[i])
        dfs(i, -1, i);

性质：

点双连通分量缩完图后是一棵树，树上每一个点是割点或是点双，每一条边表示连接原图中割点和其所在点双的边（反之亦然：每一个点双是缩完图后一个节点，每一个割点是缩完图后的一个点）。

2-sat

2-sat 是用于解决若干个或命题解的算法。

有 $n$ 个布尔变量 $a_i$ 和 $m$ 个形如 $c_j=l_{x_j}\vee l_{y_j}$ 的约束，其中 $l$ 表示变量或其否定，求使所有 $c_j$ 都为真的解。

2-sat 建边的本质是 $a\to b$ 的蕴含式，所以不局限于 $a\vee b$。

求解：

根据离散数学基础，易得：$a\vee b=\mathrm{\neg }a\to b\wedge \mathrm{\neg }b\to a$。

用 $i$ 表示 $a_i$，$i+n$ 表示 $\mathrm{\neg }{a}_i$。对于约束 $l_x\vee l_y$，分别建立 $\mathrm{\neg }{l}_x\to l_y$ 和 $\mathrm{\neg }{l}_y\to l_x$ 两条边。例如，$a_x\vee a_y$ 对应边 $(x+n,y)$ 和 $(y+n,x)$。

那么可以发现，建出来的图中，同一个强连通分量中的点取值相同：

• 如果有一个点为 $1$，易得走下去都是 $1$。
• 反之就都是 $0$。

所以原问题无解，当且仅当 $i$ 和 $i+n$ 在同一个强连通分量中。

有解时，根据拓扑序，$u\to v$，$u$ 为 $1$ 时，$v$ 一定为 $1$，$u$ 为 $0$ 时 $v$ 可以为 $1/0$。

若存在边 $(a,b)$ 那么一定存在边 $(\mathrm{\neg }b,\mathrm{\neg }a)$

若存在路径 $a\to b$ 那么一定存在路径 $\mathrm{\neg }b\to \mathrm{\neg }a$

结合上述结论，每个 SCC 与其中所有文字取反后得到的 SCC 成对出现。本文 Tarjan 代码在 SCC 弹栈时递增编号，编号越小，在缩点 DAG 的正向拓扑序中越靠后。因此可以构造

$$a_i=[nu{m}_i<nu{m}_{i+n}].$$

也就是说，在 $a_i$ 与 $\mathrm{\neg }{a}_i$ 所属的两个 SCC 中，把正向拓扑序更靠后的文字取为真。若采用按正向拓扑序递增的 SCC 编号，以上不等号需要反向，不能脱离编号约定记忆真值方向。

蕴含图有 $2n$ 个点和 $2m$ 条边，使用 Tarjan 求强连通分量并构造解的时间复杂度为 $O(n+m)$。

圆方树

仙人掌

广义圆方树