有向非连通图最小补全边数算法异常问题求助

我需要实现算法，计算从指定起始顶点出发，连通有向非连通图所有节点所需添加的最小边数。目前基于DFS的代码在小输入场景下运行正常，但处理大输入时返回错误结果（当前输出356，预期输出263），尝试过Tarjan算法也没能解决问题。

现有代码 #

#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

class Graph {
    vector<vector<int>> vertices;
public:
    Graph(int num_ver) {
        vertices.resize(num_ver);
    }

    void addEdge(int ver1, int ver2) {
        vertices[ver1].push_back(ver2);
    }

    vector<int>& getNeighbors(int ver) {
        return vertices[ver];
    }
    int getVertices() {
        return vertices.size();
    }
};

void dfs(Graph& graph, int vertex, vector<bool>& visited) {
    visited[vertex] = true;
    vector<int>& neighbors = graph.getNeighbors(vertex);
    for (int i = 0; i < neighbors.size(); i++) {
        int n = neighbors[i];
        if (!visited[n]) {
            dfs(graph, n, visited);
        }
}
}

int findMinEdges(Graph& graph) {
    int num_vertices = graph.getVertices();
    vector<bool> visited(num_vertices, false);
    int edges = 0;
    for (int i = 0; i < num_vertices; i++) {
        if (!visited[i]) {
            dfs(graph, i, visited);
            edges++;
        }
    }
    return (edges - 1);
}

int main() {
    ifstream f("input.txt");
    int vertices, edges, start;
    f >> vertices >> edges >> start;
    //cout << vertices << edges << start;'
    Graph g(vertices + 1);
    int v1, v2;
    for (int i = 0; i < edges; i ++) {
        f >> v1 >> v2;
        g.addEdge(v1, v2);
    }
    f.close();
    int min_edges = findMinEdges(g);
    cout << "Minimum number of edges to make the graph connected: " << min_edges << endl;
    ofstream o("output.txt");
    o << min_edges;
    o.close();
    return 0;
}

示例输入 #

6 5 5
1 2
2 3
3 1
4 5
5 6

输入格式说明 #

首行三个数依次为：总顶点数、总边数、起始顶点；后续每行表示一条有向边（前为起点v1，后为终点v2）。

代码错误分析 #

当前代码完全误解了有向图的连通需求：

1. 误将有向图当作无向图处理：用DFS统计的是无向连通分量数量，返回分量数-1，但这只适用于无向图的连通问题。而需求是从指定起点出发能到达所有节点，本质是处理有向图的可达性，而非无向连通性。
2. 忽略起始顶点的特殊性：代码遍历所有未访问节点的连通分量，完全没考虑这些分量是否能被起点到达，也没处理有向分量之间的入度/出度关系，这在有向图场景下逻辑完全错误。

正确解决方案 #

要解决这个问题，必须基于**强连通分量（SCC）**缩点，将原图转化为有向无环图（DAG）后计算：

步骤说明 #

1. 标记起点可达节点：从起点出发做DFS/BFS，标记所有能到达的节点。
2. 提取不可达子图：将所有未被标记的节点提取出来，构建子图。
3. 缩点为SCC：对不可达子图用Kosaraju算法找出所有强连通分量，将每个分量视为一个节点，构建缩点后的DAG。
4. 统计DAG的入度/出度：统计缩点后每个节点的入度和出度。
5. 计算最小加边数：
   • 若不可达分量数量为0，返回0；
   • 设缩点后DAG中入度为0的节点数为in_zero，出度为0的节点数为out_zero；
   • 最小边数为max(in_zero, out_zero)，但如果只有1个不可达分量，只需1条边（从起点可达区域指向它）。

修正后的代码示例 #

#include <iostream>
#include <vector>
#include <fstream>
#include <stack>
#include <algorithm>
#include <cstring>

using namespace std;

class Graph {
public:
    vector<vector<int>> adj;
    vector<vector<int>> adj_rev;
    int n;

    Graph(int num_ver) : n(num_ver) {
        adj.resize(n + 1);
        adj_rev.resize(n + 1);
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj_rev[v].push_back(u);
    }

    // Kosaraju算法找SCC
    void dfs1(int u, vector<bool>& visited, stack<int>& order) {
        visited[u] = true;
        for (int v : adj[u]) {
            if (!visited[v]) {
                dfs1(v, visited, order);
            }
        }
        order.push(u);
    }

    void dfs2(int u, int label, vector<int>& component, vector<bool>& visited) {
        visited[u] = true;
        component[u] = label;
        for (int v : adj_rev[u]) {
            if (!visited[v]) {
                dfs2(v, label, component, visited);
            }
        }
    }

    vector<int> findSCC() {
        vector<bool> visited(n + 1, false);
        stack<int> order;

        for (int u = 1; u <= n; ++u) {
            if (!visited[u]) {
                dfs1(u, visited, order);
            }
        }

        fill(visited.begin(), visited.end(), false);
        vector<int> component(n + 1, -1);
        int label = 0;

        while (!order.empty()) {
            int u = order.top();
            order.pop();
            if (!visited[u]) {
                dfs2(u, label, component, visited);
                label++;
            }
        }

        return component;
    }

    // 标记从起点可达的节点
    void markReachable(int start, vector<bool>& reachable) {
        stack<int> s;
        s.push(start);
        reachable[start] = true;

        while (!s.empty()) {
            int u = s.top();
            s.pop();
            for (int v : adj[u]) {
                if (!reachable[v]) {
                    reachable[v] = true;
                    s.push(v);
                }
            }
        }
    }
};

int main() {
    ifstream f("input.txt");
    int vertices, edges, start;
    f >> vertices >> edges >> start;

    Graph g(vertices);
    for (int i = 0; i < edges; ++i) {
        int u, v;
        f >> u >> v;
        g.addEdge(u, v);
    }
    f.close();

    // 标记起点可达的节点
    vector<bool> reachable(vertices + 1, false);
    g.markReachable(start, reachable);

    // 收集不可达节点
    vector<int> unreachable_nodes;
    for (int u = 1; u <= vertices; ++u) {
        if (!reachable[u]) {
            unreachable_nodes.push_back(u);
        }
    }

    if (unreachable_nodes.empty()) {
        cout << "Minimum number of edges to make the graph connected: 0" << endl;
        ofstream o("output.txt");
        o << 0;
        o.close();
        return 0;
    }

    // 构建不可达子图的SCC映射
    vector<int> scc = g.findSCC();
    int num_scc = *max_element(scc.begin(), scc.end()) + 1;

    // 统计每个SCC是否属于不可达区域
    vector<bool> scc_unreachable(num_scc, false);
    for (int u : unreachable_nodes) {
        scc_unreachable[scc[u]] = true;
    }

    // 构建缩点后的DAG，统计入度和出度
    vector<int> in_degree(num_scc, 0);
    vector<int> out_degree(num_scc, 0);
    vector<bool> edge_added(num_scc * num_scc, false); // 避免重复统计边

    for (int u = 1; u <= vertices; ++u) {
        if (!scc_unreachable[scc[u]]) continue;
        for (int v : g.adj[u]) {
            if (!scc_unreachable[scc[v]]) continue;
            int cu = scc[u];
            int cv = scc[v];
            if (cu != cv && !edge_added[cu * num_scc + cv]) {
                edge_added[cu * num_scc + cv] = true;
                out_degree[cu]++;
                in_degree[cv]++;
            }
        }
    }

    // 统计不可达SCC中的入度0和出度0数量
    int in_zero = 0, out_zero = 0;
    int unreachable_scc_count = 0;
    for (int i = 0; i < num_scc; ++i) {
        if (scc_unreachable[i]) {
            unreachable_scc_count++;
            if (in_degree[i] == 0) in_zero++;
            if (out_degree[i] == 0) out_zero++;
        }
    }

    int min_edges;
    if (unreachable_scc_count == 1) {
        min_edges = 1;
    } else {
        min_edges = max(in_zero, out_zero);
    }

    cout << "Minimum number of edges to make the graph connected: " << min_edges << endl;
    ofstream o("output.txt");
    o << min_edges;
    o.close();

    return 0;
}

内容的提问来源于stack exchange，提问作者BlueBerryPie