RAHUL - 1 year ago 63
C++ Question

# representing graph in c++ using vector<vector>

I'm trying to represent an undirected graph in c++ and then printing the vertices with their neigbours. But when i'm unable to understand the output here-

``````#include <iostream>
#include <vector>

using namespace std;

int reach(vector<vector<int> > &adj) {
vector<vector<int> >::iterator it;
vector<int>::iterator i;
for (it = adj.begin(); it != adj.end(); ++it)
{
cout << (*(*it).begin()) << "outside"<< endl;

for (i = (*it).begin(); i != (*it).end(); ++i)
{
cout << (*i) << "inside" << endl;

}
}
return 0;
}

int main() {
size_t n, m;
cin >> n >> m;
vector<vector<int> > adj(n, vector<int>());
for (size_t i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
adj[x - 1].push_back(y - 1);
adj[y - 1].push_back(x - 1);
}
}
``````

outside means it's the vertex and inside are its neigbours.

``````for the input 3 2 1 2 2 3 output is-

1outside
1inside
0outside
0inside
2inside
1outside
1inside
``````

why is 1outside there 2 times ? And shouldn't the output be

``````0outside
1inside
1outside
0inside
2inside
2outside
1inside
``````

It appears that your intent is for the first dimension of your two-dimensional vector to be the identity of the first point, with all second points, that the first point leads to, stored in the second dimension.

``````cout << (*(*it).begin()) << "outside"<< endl;
``````

This does not print the value of the first dimension being iterated over. This prints the first value of the second dimension. Which is why you get duplicate output.

`it` is a random access iterator of the vector comprising the identify of the first point. If so,

`````` cout << (it-adj.begin()) << "outside"<< endl;
``````

will reverse-engineer its index. But that's going to be too confusing.

It's more straightforward to rewrite the whole thing using index iteration on the outside, and range iteration on the inside:

``````for (size_t i=0; i<adj.size(); ++i)
{
cout << i << "outside"<< endl;

for (auto j: adj[i])
cout << j << "inside" << endl;
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download