有向图转强连通图最少加边数

原文链接

问题描述

对于一有向图，若需要保证任选一点即可走到其它所有点，询问最少需要加多少条有向边

结论

对于一有向图，若其对应DAG中入度为0的点数为$p$，出度为0的点数为$q$，则答案数为$max(p, q)$

证明： $p \leq q$ 和 $p \geq q$的证明过程类似，这里仅说明$p \leq q$的证明过程

1. 当$p == 1$，即1个起点，2个及以上终点时。可知起点就是一个链式关系中最前面的节点，从起点可到达链式关系中的任一点，因此从每一个终点向起点连接一条边即可实现强连通，答案为$q$
2. 当$p > 1$时，$q \geq p > 1$，即2个及以上起点，2个及以上终点，且满足$终点数>=起点数$ 此时需要考虑一种特殊情况，$p == q == 2$。设两个起点分别为$p_1, p_2$，两个终点分别为$q_1, q_2$，则一定存在一种方案使得$p_1$可以走到$q_1$, $p_2$可以走到$q_2$，证明采用反证法，假设$q_2$无法从$p_1$和$p_2$走到，但由于此图是一DAG，对于$q_2$，不停找其前驱节点最终一定可以找到某个节点是走向$q_2$的，且该节点入度为$0$，即是一个起点，这与所有起点都无法到达$q_2$的假设相矛盾 如果添加一条$q_1 -> q_2$的边,则问题转化为$p == 1$的情况,还需要添加$1$条边,故答案为$2$ 综上所述, 一种可行的操作方法为将$p > 1$的情况转化为$p == 1$,具体方法为将$(p - 1)$个终点连向起点,这一步需要添加$(p - 1)$条边 此时起点数为$1$,终点数为$q - (p - 1)$, 还需要添加$q - (p - 1)$条边 综上,答案数为$q - (p - 1) + (p - 1) = q = max(p, q)$

解决思路

由上述结论可知，我们仅需将原图转变为DAG，分别统计入度为$0$和出度为$0$的点数即可 有向图转DAG可采用Tarjan实现

例题解析

题目描述

解题思路 第1问： 假如当前图为有向无环图，那么只需要计算入度为0的点的个数即可 因为对于入度非0的点，我们只需要将软件提供给它的前驱即可，对于它的前驱同理，依次类推，我们仅需要提供给该链式关系中的第一个节点即可，而链式关系中的第一个节点即为入度为0的点，故需要统计的就是入度为0的点的个数

第2问： 对题目描述进行抽象可得目标为计算“有向图转变为强连通图所需的最少加边数”，即为$max(入度为0点数，出度为0点数)$ 将有向图转为强连通图，并分别统计入度和出度分别为0的个数即可

代码实现

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>

using namespace std;

const int N = 110, M = 5000;

int n, m;
int h[N], e[M], ne[M], idx;
stack<int> stk;
int timestamp;
bool in_stk[N];
// tarjan维护值
int dfn[N], low[N];
int id[N], Size[N], scc_cnt;
// 统计入度出度
int din[N], dout[N];

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}
void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;
    stk.push(u), in_stk[u] = true;

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (in_stk[j]) low[u] = min(low[u], dfn[j]);
    }

    if (dfn[u] == low[u])
    {
        ++ scc_cnt;
        int y;
        do {
            y = stk.top(); stk.pop();
            in_stk[y] = false;
            id[y] = scc_cnt;
            ++ Size[scc_cnt];
        }while (y != u);
    }
}
int main()
{
    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 1; i <= n; ++ i)
    {
        int y;
        while (cin >> y, y) add(i, y);
    }
    
    for (int i = 1; i <= n; ++ i)
        if (!dfn[i])
            tarjan(i);
    
    // 统计入度为0的点数p，出度为0的点数q
    int p = 0, q = 0;
    for (int i = 1; i <= n; ++ i)
        for (int j = h[i]; ~j; j = ne[j])
        {
            int t = e[j];
            int a = id[i], b = id[t];
            if (a != b)
            {
                ++ dout[a];
                ++ din[b];
            }
        }
    
    for (int i = 1; i <= scc_cnt; ++ i)
    {
        if (!din[i]) ++ p;
        if (!dout[i]) ++ q;
    }

    cout << p << endl;
    if (scc_cnt == 1) cout << 0 << endl; // 仅有一个scc，不需要连边，如果按照max(p, q)输出是错误的，需要特判
    else cout << max(p, q) << endl;
    
    return 0;
}