CODEWITHSUNDEEP
c++stl
Shashank
Shashank

Reputation: 166

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);
  }
  cout << reach(adj);
}

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

Upvotes: 1

Views: 1901

Answers (1)

Sam Varshavchik
Sam Varshavchik

Reputation: 118340

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

Upvotes: 3

Related Questions