Kosaraju算法求SCC：两段逻辑一致的代码为何一个超时？

我在解决求有向图强连通分量数量的问题时，写了两段逻辑看似一致的Kosaraju算法代码，第一段能正常通过所有测试用例，第二段却出现了Time Limit Exceeded错误，求帮忙分析原因。

第一段可正常运行的代码 #

void dfs(int node, vector<vector<int>>& adj, stack<int>& st, vector<bool>& vis) {
    vis[node] = 1;
    for (auto &it : adj[node]) {
        if (!vis[it]) dfs(it, adj, st, vis);
    }
    st.push(node);
}

void dfs2(int node, vector<vector<int>>& adj, vector<bool>& vis) {
    vis[node] = 1;
    for (auto &it : adj[node]) {
        if (!vis[it]) dfs2(it, adj, vis);
    }
}

int kosaraju(int V, vector<vector<int>>& adj) {
    vector<bool> vis(V, 0);
    stack<int> st;

    // First DFS to fill the stack with the finishing times
    for (int i = 0; i < V; i++) {
        if (!vis[i]) dfs(i, adj, st, vis);
    }

    // Create the transpose of the graph
    vector<vector<int>> adjRev(V);
    for (int i = 0; i < V; i++) {
        for (auto &it : adj[i]) {
            adjRev[it].push_back(i);
        }
    }

    // Second DFS to count the number of SCCs
    int cnt = 0;
    vis = vector<bool>(V, 0);
    while (!st.empty()) {
        int node = st.top();
        st.pop();
        if (!vis[node]) {
            dfs2(node, adjRev, vis);
            cnt++;
        }
    }
    return cnt;
}

第二段超时的代码 #

private:
    int dfs(int v, stack<int> &s, vector<int> &vis, vector<vector<int>> g){
        vis[v] = 1;
        for(auto child : g[v]){
            if(vis[child]  == 0){
                dfs(child, s, vis, g);
            }
        }
        s.push(v);
    }
    int DFS(int v, vector<int> &vis, vector<vector<int>> g){
        vis[v] = 1;
        for(auto child : g[v]){
            if(vis[child]  == 0){
                DFS(child, vis, g);
            }
        }
    }
    public:
    //Function to find number of strongly connected components in the graph.
    int kosaraju(int V, vector<vector<int>>& adj)
    {
        stack<int> s;
        vector<int> vis(V, 0);
       for(int i =0; i<V; i++){
           if(vis[i] == 0)  dfs(i, s, vis, adj);
       }
        vector<vector<int>> g(V);
        for(int i =0; i<V; i++){
            vis[i] =0;
            for(auto y : adj[i]){
                g[y].push_back(i);
            }
        }
        int ct =0;
        while(!s.empty()){
            int x = s.top();
            s.pop();
            if(vis[x] == 0){
                DFS(x, vis, g);
                ct++;
            }
        }
        return ct;
    }

超时原因分析 #

两段代码的核心差异在于图的传递方式：

• 第一段代码的dfs和dfs2函数中，图参数用的是引用传递（vector<vector<int>>& adj），递归调用时不会复制整个图结构，只是传递指向原数据的引用，时间和空间开销极小。
• 第二段代码的dfs和DFS函数中，图参数用的是值传递（vector<vector<int>> g），每次递归调用都会完整复制整个图。对于顶点和边数较多的测试用例，这种复制会带来巨大的时间和内存开销——递归深度可能达到O(V)，每次复制的时间是O(V+E)，总时间复杂度会从正常的O(V+E)飙升到O(V*(V+E))，直接导致超时。

另外还有两个非核心的语法隐患，但不是超时的直接原因：

1. 第二段的dfs和DFS函数声明返回int，但实际没有返回值。
2. 第一段用vector<bool>作为访问标记，第二段用vector<int>，前者空间更优，但对运行时间影响可以忽略。

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