Given an undirected graph G(V,E), find and print all the connected components of the given graph G

Question

This is the question I am trying to code. I have written the following code but I don't know how can I store the elements in the vector in getComponent() function and retrieve it inside main function.

I have used ans as a vector variable. I am passing its address so that I do not have to return anything. But I am getting compilation error while running the code.

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

Careful with `#include `. You're not using it correctly. Usually best [if you don't use it at all.](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) — user4581301, May 16 '22 at 02:42
`int **edges = new int *[n];` -- `edges[i] = new int[n];` -- You included ``, but it seems you missed the entire purpose of using vector. The `std::vector` class removes you having to write code like this. For example `std::vector> edges(n, std::vector(n));` does all of the work you are doing with `new[]`. The same thing here: `int *visited = new int[n];`. This could simply be `std::vector visited(n);`. Bottom line -- don't use "competitive coding" websites to learn C++ programming. — PaulMcKenzie, May 16 '22 at 03:03

score 0 · Answer 1 · answered May 16 '22 at 02:32

You need to actually create an ans vector and pass it's address:

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

After that you should replace all C-style arrays with std::vector and pass references instead of pointers.

Given an undirected graph G(V,E), find and print all the connected components of the given graph G

1 Answers1