смежности список представление с использованием вектора векторов (2D вектор) в C++

Question

Мы можем заполнить список смежности в BFS с помощью 1D вектор как vector<int> adj[10]; мы можем заполнить этот вектор следующим образом:

main(){ 
int x,y,nodes,edges; 
cin>>nodes>>edges; 
for(int i=0;i<edges;i++){ 
cin>>x>>y; 
adj[x].push_back(y); //Insert y in adjacency list of x 
} 
} 

Теперь, как мы можем использовать 2D вектор (или вектор векторов), чтобы заполнить список смежности вместо 1D-вектора для 2D-вектор be может быть как vector<vector<int> >g; Итак, как мы можем заполнить этот 2D-вектор для построения списка смежности?

Answer 1

Скажем, максимальное значение x может быть n.
Сначала вы должны инициализировать 2D-вектор с n Число 1D-вектор.
Затем вы можете выполнять операции, подобные тому, что вы делали в вашем примере.

vector<vector<int> >g; 
for(int i = 0; i<n; i++) 
{ 
    vector<int>v; 
    g.push_back(v); 
} 

g[0].push_back(3); 
g[1].push_back(5); 
cout<<g[0][0]<<endl; 
cout<<g[1][0]<<endl; 

Или вы можете инициализировать вектор во время объявления.

vector<vector<int> >g(n); 

g[0].push_back(3); 
g[1].push_back(5); 
cout<<g[0][0]<<endl; 
cout<<g[1][0]<<endl;