Блог

Главная - Вопросы по программированию - Почему необходимо передавать вектор anc по ссылке в функции dfs?

Почему необходимо передавать вектор anc по ссылке в функции dfs?

#graph #depth-first-search #cycle

Вопрос:

 class Solution
{
    public:
    //Function to detect cycle in a directed graph.
    bool dfs(int V, vector<int> adj[],vector <bool>amp; isvis,int start,vector<bool>**amp;**anc)
    {
        isvis[start]=1;
        anc[start]=true;
        for(auto nb : adj[start])
        {   
                
            if(!isvis[nb])
            {
                if(dfs(V,adj,isvis,nb,anc))
                return true;
            }
            
            if(anc[nb]==true)
                return true;
        }
        
        for(int i=0;i<V;i  )
        {
            cout<<i<<" "<<anc[i]<<endl;
        }
        
        anc[start]=false;
        return false;
    }
    bool isCyclic(int V, vector<int> adj[]) 
    {
       vector < bool > isvis(V,false);
       vector <bool> anc(V,false);
       for(int i=0;i<V;i  )
       {
           if(!isvis[i])
           {
               if(dfs(V,adj,isvis,i,anc))
               return true;
           }
       }
       return false;
    }
};

Ответ №1:

Потому что функция изменяет аргумент (in anc[start]=true; ). Если бы он был передан по значению, у него была бы своя собственная копия вектора и он изменил бы эту копию, поэтому anc переменная in isCyclic не была бы изменена.

Комментарии:

1. Мы просто используем вектор anc для отслеживания узлов-предков соседей adj, поэтому нам нужно его изменить

2. А также я не получаю неправильного ответа, но я получаю TLE

3. Опять же, потому что у вас есть anc[start]=true; (а также anc[start]=false; ближе к концу и рекурсивный dfs вызов, который также изменит anc isvis векторы и).

4. Вы можете написать другую реализацию, которая этого не делает, а затем передать anc ее по значению (но было бы более распространено передавать ее по постоянной ссылке, чтобы избежать копирования).

Метки: