时间戳

首页 > 技术文章 > 有向图转强连通图最少加边数

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

G-H-Y 2021-09-15 16:19 原文

问题描述

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

结论

对于一有向图，若其对应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;
}

推荐阅读