递归函数中未按引用传vector引发Time Limit Error的原因探究

在解决有向图环检测问题时，我们使用两个数组：

• vis：标记所有已访问过的节点，避免重复遍历
• pvis：标记当前递归路径上的节点，用于检测环（若遍历到已在pvis中的节点，则说明存在环）

第一种实现（正常运行无超时） #

将vis和pvis均按引用传递，递归回溯时重置pvis的标记：

bool dfs(int i ,vector<int> adj[] , vector<int> &vis,vector<int> &pvis, int V)
{
    vis[i]=1;
    pvis[i]=1;
    bool temp;
   for(int j = 0 ; j< adj[i].size() ; j++)
   {    
       
       if(vis[adj[i][j]]==0)
       {
           if(dfs(adj[i][j], adj, vis, pvis,V)== true)
           {
               return true;
           }
       }
       else if(pvis[adj[i][j]]==1)
       {
            return true;
       }
   }
   pvis[i] = 0;
   return false;
}

bool isCyclic(int V, vector<int> adj[]) {
    vector<int> vis(V,0);
    vector<int> pvis(V,0);
    for(int i = 0; i< V ;i++)
    {
        if(vis[i]==0)
        {
            if(dfs(i,adj,vis,pvis,V)==true)
            {
                return true;
            }
        }
    }
    return false;
}

第二种实现（运行超时） #

仅将vis按引用传递，pvis按值传递（每个递归调用拥有本地副本，无需回溯重置）：

bool dfs(int i ,vector<int> adj[] , vector<int> &vis,vector<int> pvis, int V)
{
    vis[i]=1;
    pvis[i]=1;
    bool temp;
   for(int j = 0 ; j< adj[i].size() ; j++)
   {    
       
       if(vis[adj[i][j]]==0)
       {
           if(dfs(adj[i][j], adj, vis, pvis,V)== true)
           {
               return true;
           }
       }
       else if(pvis[adj[i][j]]==1)
       {
            return true;
       }
   }
   return false;
}

bool isCyclic(int V, vector<int> adj[]) {
    vector<int> vis(V,0);
    vector<int> pvis(V,0);
    for(int i = 0; i< V ;i++)
    {
        if(vis[i]==0)
        {
            if(dfs(i,adj,vis,pvis,V)==true)
            {
                return true;
            }
        }
    }
    return false;
}

差异原因分析 #

两种实现的逻辑正确性是一致的，但性能上有天壤之别，第二种实现超时的核心原因是**pvis按值传递带来的拷贝开销**：

1. 按值传递vector时，每次递归调用都会创建一个新的pvis副本，复制整个数组的所有元素。当图的节点数V较大（比如上万级）时，单次拷贝的时间开销就很高。
2. 递归深度越大，拷贝操作的总次数越多，累计的时间开销会呈指数级增长，最终超出题目时间限制。
3. 第一种实现通过引用传递共享同一个pvis数组，仅在回溯时修改单个元素的标记，几乎没有额外开销，内存占用也远低于第二种实现。

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