#include<bits/stdc  .h>
using namespace std;
const int N=1e3;
vector <int> graph2[N];
int main(){
    int n,m;
    cin>> n>>m;
    for(int i=0;i<m;i  ){
        int v1,v2;
        cin>>v1>>v2;
        graph2[v1].push_back(v2);
        graph2[v2].push_back(v1);
    }
    for(int i=1;i<=6;i  ){
        for(int j=0;j<graph2[i].size();j  ){
            cout<<graph2[i][j]<<" ";
        }
        cout<<endl;
    }
}

I am creating a adjacency list representation of a tree and using above code and found on the internet that its space complexity is O(V E) not O(E) why? I am only using the vector for storing edges like--

Input-  
6 9
1 3
1 5
3 5
3 4
3 6
3 2
2 6
4 6
5 6

Output - 
3 5 
3 6 
1 5 4 6 2 
3 6 
1 3 6 
3 2 4 5 

I am using only storing the one part as v1---v2 then only storing v2 and v1 is the index by default so why we are assuming v1 in our space complexity?

CodePudding user response：

You're using a fixed N and ignoring n, which makes it look like the space complexity doesn't depend on the number of vertices (you are essentially saying "every graph has 1000 vertices").

If you use a local vector<vector<int>> graph(n);, you see how the required space depends on n.

CodePudding user response：

An adjacency list representation of a graph should be an array where every cell represents the name of a vertex of the graph, so you have an array of |V| size, then every element of the array is linked to a list that contains all the edges starting from the vertex represented by the cell of the array.

So, in total, you have an array of |V| size and |E| nodes representing all the edges starting from each vertex ( O(|V| |E|) ).

I hope I was clear.