Нахождение минимальной стоимости в графе с использованием DFS

Question

Я пытаюсь решить эту проблему на хакерранке о подсчете минимальных затрат на создание библиотек во множестве соединенных городов, которые пострадали от торнадо.Я использую DFS для поиска на графике и поиска количества подключенных компонентов (или городов в данном случае) и получения окончательной стоимости.Существует также условие, при котором стоимость строительства библиотек в каждом городе меньше, чем строительство дорог для связи людей с библиотекой в ​​любом другом городе.В этом случае я просто вывел стоимость строительства каждой библиотеки, умноженную на количество городов.Ссылка на проблему: https://www.hackerrank.com/challenges/torque-and-development/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=graphs

По какой-то причине, когда мой код переходит в раздел else, когда я пытаюсь построить список смежности для каждого города, выходной терминал преждевременно завершается.Моя логика неверна, или есть какая-то проблема с областью действия.Класс, в котором определены переменные и функция dfs ():

class minCost{
    public:
        vector<vector<int>>adjCities;
        int connComps;
        vector<bool>visited;

        void dfs(int city){
            visited[city]=true;
            for(int i=0;i<adjCities[city].size();i++){
                while(!visited[adjCities[city][i]]){
                    dfs(adjCities[city][i]);
                }
            }
        }
};

Остальная часть логики в методе main ():

int main(){
    int q;
    cin>>q;
    for(int i=0;i<q;i++){
        minCost cst;
        int c,r,c_lib,c_road;
        cin>>c>>r>>c_lib>>c_road;
        if(c_lib<=c_road || r==0){
            cout<<c_lib*c<<"\n";
        continue;
        }
        else{
            for(int i=0;i<r;i++){   //does not loop for r=(no. of roads) times
                int c1,c2;
                cin>>c1>>c2;
                cst.adjCities[c1].push_back(c2);
                cst.adjCities[c2].push_back(c1);
            }
            for(int i=1;i<=c;i++){
                if(!cst.visited[i]){
                    cst.dfs(i);
                    cst.connComps++;
                }
            }
            cout<<c_road*(c-cst.connComps)+c_lib*cst.connComps<<"\n";
        }
    }
    return 0;
}

Answer 1

Вы не объявили размер вектора соседей и посетили. Но вы, когда пытаетесь использовать его, он находит индекс невыделенного массива. Просто инициализируйте размер этих двух векторов. После этой строки cin >> c >> r >> c_lib >> c_road; , добавьте эти две строки -

cst.adjCities.resize(c+1);
cst.visited.resize(c+1);
cst.connComps = 0;

Надеюсь, это поможет.