CODEWITHSUNDEEP
c++graph
harshrd
harshrd

Reputation: 79

Finding minimum cost in graph using DFS

I am trying to solve this problem on hackerrank about calculating min cost for building libraries across a host of connected cities which have been affected by a tornado. I am using DFS to search the graph and look for the number of connected components (or cities in this case) and getting the final cost. There is also a condition where the cost of building libraries at each city is lesser than building roads to connect people to library in any other city. In that case I have simply output the cost of building each library multiplied by number of cities. The link to the problem: https://www.hackerrank.com/challenges/torque-and-development/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=graphs

For some reason, when my code goes into the else section, when I am trying to build the adjacency list for each city, the output terminal exits prematurely. Is my logic incorrect, or is there some sort of scope issue. The class where variables and function dfs() is defined:

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]);
                }
            }
        }
};

The rest of the logic in the main() method:

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;
}

Upvotes: 0

Views: 715

Answers (1)

Faruk Hossain
Faruk Hossain

Reputation: 1203

You didn't declare size of the vector of adjCities and visited. But you when are trying to use it it finds unallocated array index. Just initialise the size of these two vectors. After this cin>>c>>r>>c_lib>>c_road; line, add these two lines - 

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

Hope this will help.

Upvotes: 3

Related Questions