深入研究：如何添加最少的边，使 DAG 变成强连通图

farfarqwq · 2025-12-21 20:53:07 · 算法·理论

题目大意

给定一张有向图，添加最少数量的有向边，使图强连通。

求出这个最小的边数并输出方案。

解法

先缩点，每个强连通分量显然可以当成一个点考虑。

我们声称答案是缩点后形成的 DAG 上，0 入度点数量和 0 出度点数量的较大值（孤立点同时作为 0 入度点和 0 出度点）。

特别地，在整张图一开始就强连通（即缩完点后只剩一个点）的情况下答案是 0。

为方便，设 0 入度点集合为 S，0 出度点集合为 T。用 u\to v 表示 u 能到 v。

不妨设 |S|\le|T|，现在有一个足够简单的 O(nm) 时间复杂度的构造：

:::info[O(nm) 的构造]

• 假设当前 |S|\ge 2，则必能找到两个不同的 0 入度点 a_1,a_2，两个不同的 0 出度点 b_1,b_2，满足 a_1\to b_1,a_2\to b_2。添加边 (b_1,a_2)，此时 S,T 的大小均减少 1。
• 若 |S|=1，设该唯一的 0 入度点为 x，则该图一定形成一个菊花（x 可以到达所有 0 出度点），将所有 0 出度点向 x 连边即可。|T|=1 同理。

发现每次连边恰好使 T 集合减少 1，且最后整张图强连通，符合我们的要求。

但是每加一条边都要动态维护连通性，所以该算法时间复杂度是 O(nm) 的。 :::

考虑优化复杂度，下面给出两种复杂度线性的做法。

:::info[Sol1]

• 遍历 S 集合，从其中每个 0 入度点 x 开始 dfs，随便找一个 x 能到达的 0 出度点，记为 to_x，并将 x 和 to_x 路径上所有点删去。若没能找到 0 入度点，to_x=0。

  容易发现 to_x 非零元素互不相同，且所有 to_x=0 的 0 入度点必能到达一个 to 中的 0 出度点；所有没在 to 中出现的 0 出度点必能被一个 to_x\neq 0 的 0 入度点到达。

• 于是同下图，我们将所有 x\to to_x 形成的匹配首尾相连成一个环，然后再将空闲的 0 入度点与空闲的 0 出度点随便两两匹配，最后剩下一些没有匹配上的 0 出度点，直接向刚刚形成的大联通块连边即可。
• 容易证明刚刚同样一共连了 |T| 条边。

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000005;
int cnt, head[N], h2[N];
struct edge {
    int v, next;
} e[N << 2];
inline void add(int u, int v, int *head) {
    e[++cnt].v = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}
int tot, num, dfn[N], low[N], scc[N], id[N];
int t, s[N];
bool vis[N], ok[N];
int in[N], out[N];
void dfs(int p) {
    dfn[p] = low[p] = ++tot;
    vis[s[++t] = p] = 1;
    for (int i = head[p]; i; i = e[i].next) {
        int v = e[i].v;
        if (!dfn[v]) {
            dfs(v);
            low[p] = min(low[p], low[v]);
        } else if (vis[v]) {
            low[p] = min(low[p], dfn[v]);
        }
    }
    if (low[p] == dfn[p]) {
        int x;
        id[++num] = p;
        ok[p] = 1;
        do {
            x = s[t--];
            scc[x] = p;
            vis[x] = 0;
        } while (x != p);
    }
}
int tt, r1[N][2];
bool vv[N];
int dfs2(int p) {
    if (vis[p])
        return 0;
    vis[p] = 1;
    if (!out[p])
        return p;
    for (int i = h2[p]; i; i = e[i].next) {
        int tmp = dfs2(e[i].v);
        if (tmp)
            return tmp;
    }
    return 0;
}
int t1, t2, n1[N], n2[N];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        add(u, v, head);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i])
            dfs(i);
    }
    for (int i = 1; i <= n; i++)
        for (int j = head[i]; j; j = e[j].next) {
            int v = e[j].v;
            if (scc[i] == scc[v])
                continue;
            add(scc[i], scc[v], h2);
            ++in[scc[v]];
            ++out[scc[i]];
        }
    if (num <= 1) {
        cout << "0\n";
        return 0;
    }
    int c0 = 0, c1 = 0;
    int o = 0;
    for (int j = 1; j <= num; j++) {
        int i = id[j];
        if (!in[i]) {
            ++c0;
            int y = dfs2(i);
            if (y)
                r1[++tt][0] = i, r1[tt][1] = y, vv[i] = vv[y] = 1, o = i;
        }
        if (!out[i])
            ++c1;
    }
    cout << max(c0, c1) << '\n';
    for (int i = 1; i < tt; i++)
        cout << r1[i][1] << ' ' << r1[i + 1][0] << '\n';
    cout << r1[tt][1] << ' ' << r1[1][0] << '\n';
    for (int i = 1; i <= n; i++)
        if (ok[i] && !vv[i]) {
            if (!in[i])
                n1[++t1] = i;
            else if (!out[i])
                n2[++t2] = i;
        }
    for (int i = 1; i <= min(t1, t2); i++)
        cout << n2[i] << ' ' << n1[i] << '\n';
    for (int i = t1; i > t2; i--)
        cout << o << ' ' << n1[i] << '\n';
    for (int i = t2; i > t1; i--)
        cout << n2[i] << ' ' << o << '\n';
    return 0;
}

::: :::info[Sol2] 沿用 O(nm) 解法的核心思想每次合并两组匹配变成一组，考虑维护当前的匹配增量合并。

对 S 中的每个元素记录 out_x 表示它能到的某一个 0 出度点（任意一个即可），同理对 T 中每个元素记录 in_x 表示某一个能到他的 0 入度点。

一开始随便找到一个二元组 (x,z=out_x) 作为当前的匹配。接着每次拿一个 (y,out_y) 出来。有一个美好的幻想是每次拿出来的 out_y 都没有出现过，这样我们就可以直接 z 向 y 连边，把 (x,out_y) 当成新的匹配。最后仍然会剩下一个菊花。

但是幻想破灭，即 out_y 在 x 到 z 的路径上，注意不是 out_y=z，因为要求是 out_y 没有被合并过。这时候 y 能到达 z，我们维护的结构变成了一个三元组 (x,y,z)。拿出一个 0 出度点 k：

• 若 in_k 不属于 x 且 in_k\neq y（注意这里 x 指代的是和 x 合并过的所有点，在图上表现为一条从 x 到 z 的路径），我们直接将 in_z 合并到 x 即可（z 向 in_k 连边）。新的三元组变成 (x,y,k)。
• 若 in_k=y，则 (x,z),(y,k) 形成两组匹配，z 向 y 连边，当前结构又变回二元组 (x,k)。
• 若 in_k\in x，(x,k),(y,z) 形成两组匹配，k 向 y 连边，当前结构变回二元组 (x,z)。

不断维护二元组和三元组即可。有一些细节：

• 取出来的 0 入度点或 0 出度点已经在三元组里就可以直接忽略。
• 当无法取出符合要求的点时（在二元组时没有合法的 0 入度点，三元组时没有合法的 0 出度点），整张图必然只剩一个菊花，直接合并即可。

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000005;
vector<int> adj[N], adjo[N], adji[N];
int tot, num, dfn[N], low[N], scc[N], id[N];
int t, s[N];
bool vis[N], ok[N];
void dfs(int p) {
    dfn[p] = low[p] = ++tot;
    vis[s[++t] = p] = 1;
    for (int v : adj[p]) {
        if (!dfn[v]) {
            dfs(v);
            low[p] = min(low[p], low[v]);
        } else if (vis[v]) {
            low[p] = min(low[p], dfn[v]);
        }
    }
    if (low[p] == dfn[p]) {
        int x;
        id[++num] = p;
        ok[p] = 1;
        do {
            x = s[t--];
            scc[x] = p;
            vis[x] = 0;
        } while (x != p);
    }
}
int in[N], out[N];
int dfs2(int p, int *col, vector<int> *adj) {
    if (col[p])
        return col[p];
    if (!adj[p].size())
        return col[p] = p;
    for (int v : adj[p]) {
        int tmp = dfs2(v, col, adj);
        if (tmp)
            return col[p] = tmp;
    }
    return 0;
}
int a0[N], a1[N];
bool vv[N];
int res;
inline void link(int u, int v) {
    cout << u << ' ' << v << '\n';
    vv[u] = vv[v] = 1;
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].emplace_back(v);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i])
            dfs(i);
    }
    for (int i = 1; i <= n; i++)
        for (int v : adj[i]) {
            if (scc[i] == scc[v])
                continue;
            adjo[scc[i]].emplace_back(scc[v]);
            adji[scc[v]].emplace_back(scc[i]);
        }
    if (num <= 1) {
        cout << "0\n";
        return 0;
    }
    int c0 = 0, c1 = 0;
    int o = 0;
    for (int j = 1; j <= num; j++) {
        int i = id[j];
        if (!adji[i].size()) {
            a0[++c0] = i;
            dfs2(i, out, adjo);
        }
        if (!adjo[i].size()) {
            a1[++c1] = i;
            dfs2(i, in, adji);
        }
    }
    cout << max(c0, c1) << '\n';
    int p0 = 2, p1 = 1;
    int x = a0[1], y = 0, z = out[x];
    vv[x] = 1;
    while (1) {
        if (y) {
            if (p1 > c1)
                break;
            int k = a1[p1++];
            if (vv[k] || k == z)
                continue;
            if (vv[in[k]])
                link(k, y), y = 0;
            else if (in[k] == y)
                link(z, y), y = 0, z = k;
            else
                link(z, in[k]), z = k;
        } else {
            if (p0 > c0)
                break;
            int k = a0[p0++];
            if (vv[k])
                continue;
            if (vv[out[k]])
                out[k] = z;
            // 如果 out[k] 是 x->z 路径上的点不妨设 out[k]=z
            if (out[k] == z)
                y = k;
            else
                link(z, k), z = out[k];
        }
    }
    link(z, x);
    if (y)
        link(z, y);
    while (p0 <= c0) {
        int k = a0[p0++];
        if (!vv[k])
            link(z, k);
    }
    while (p1 <= c1) {
        int k = a1[p1++];
        if (!vv[k] && k != z)
            link(k, z);
    }
    return 0;
}

:::

可以总结上面几种做法都是先“打包”处理，最后再挨个合并单点，虽然细节不同，但都深刻发掘了一般图可达性的性质。还是很有思考价值的。