先简单介绍一下 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 是深度优先，所以可以出现后代被遍历过。

环

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

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

强连通分量

定义：

强连通：任意两个结点连通。

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

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 的拓扑排序就是 dfn 的逆序，参见 dfs 版拓扑排序，所以缩点后的 DAG 拓扑序就是 SCC 编号的降序。

杂谈：

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

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

$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：

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

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

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

对于 $(u,v)$，$lo{w}_v\le df{n}_v$，若 $lo{w}_v<df{n}_u$，则删除 $u$ 不会使 dfs 树变成两部分，所以只有 $lo{w}_v=df{n}_u$ 或 $lo{w}_v=df{n}_v$ 时，$u$ 是割点，将递归 $v$ 后栈中的点弹出形成一个点双连通分量。

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

具体而言：

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

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 : p[x]) {
        if (u == y)
            continue;
        if (!dfn[u]) {
            dfs(u, x, root);
            low[x] = min(low[x], low[u]);
            if (low[u] == dfn[x] || low[u] == dfn[u]) {
                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, 0, i);

性质：

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

2-sat

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

有 $n$ 个命题 $c_i=a_{x_i}\vee a_{y_i}$，$a,b\in \{0,1\}$，求解 $c_i$ 全为真的解。

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$，那么建边 $(x_i+n,y_i)$ 表示 $a_{x_i+n}$ 为 $1$ 时 $a_{y_i}$ 为 $1$，$a_{x_i+n}$ 为 $0$ 时，$a_{y_i}$ 可 $1$ 可 $0$。建边 $(y_i+n,x_i)$ 同理。

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

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

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

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

特别地，$a$ 和 $\mathrm{\neg }a$ 必有一真一假，若 $\mathrm{\neg }a$ 的拓扑序更小，则 $\mathrm{\neg }a$ 为 $0$，$a$ 为 $1$。

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

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

结合上述结论，可以发现，2-sat 建出来的图是一个很特殊的图。具体地，对于一个连通分量，一定存在一种划分方式，使得所有 $a$ 和 $\mathrm{\neg }a$ 会被划分至“左右”两侧。

那么，对于 $\mathrm{\neg }a$ 的拓扑序小于 $a$，构造 $a=1,\mathrm{\neg }a=0$ 即可。

使用 Tarjan 维护强连通分量，时间复杂度：$O(n)$。

圆方树

仙人掌

广义圆方树