给定一个无向图G(V,E)，找出并打印出给定图G的所有连通分量

Question

这是我试图编码的问题。我已经编写了以下代码，但我不知道如何在getComponent()函数中存储向量中的元素并在main函数中检索它。

我使用ans作为向量变量。我正在传递它的地址，这样我就不必返回任何东西。但我得到编译错误，而运行代码。

#include<vector>
#include <bits/stdc++.h>
using namespace std;
void getComponent(int **edges, int n, int sv, int * visited, vector<int>*ans){
visited[sv] = 1;

ans->push_back(sv);
for(int i = 0; i < n; i++){
if(i == sv)continue;

if(edges[sv][i] == 1){
if(visited[i] == 0)
getComponent(edges, n, i, visited, ans);
}
}
}
int main() {
// Write your code here

int n, e;
cin>>n>>e;

int **edges = new int *[n];

for(int i = 0; i < n; i++){
edges[i] = new int[n];
for(int j = 0; j < n; j++){
edges[i][j] = 0;
}
}

for(int i = 0; i <e; i++){
int a, b;
cin>>a>>b;

edges[a][b] = 1;
edges[b][a] = 1;
}

int *visited = new int[n];

for(int i = 0; i < n; i++)
visited[i] = 0;



for(int i = 0; i < n; i++){
if(visited[i] == 0){
vector<int>*ans;
getComponent(edges, n, i, visited, ans);
for (auto x : ans)
cout << x << " ";
cout<<endl;
}

}
}

Answer 1

你需要实际创建一个ans向量并传递它的地址:

for(int i = 0; i < n; i++){
if(visited[i] == 0){
vector<int> ans;
getComponent(edges, n, i, visited, &ans);
for (auto x : ans)
cout << x << " ";
cout<<endl;
}

}

之后，你应该用std::vector替换所有c风格的数组，并传递引用而不是指针。