使用 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

您没有声明 adjCities 向量的大小并访问过。但是当你尝试使用它时，它会找到未分配的数组索引。 只需初始化这两个向量的大小。 在此cin>>c>>r>>c_lib>>c_road;行之后，添加以下两行 -

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

希望这会有所帮助。