c++ - 在 C++ 中使用 vector 表示图形

Question

我试图用 C++ 表示一个无向图，然后用它们的邻居打印顶点。但是当我无法理解这里的输出时-

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

外面意味着它是顶点，里面是它的邻居。

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

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

为什么 1outside 有 2 次？输出不应该是

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

Answer 1

您的意图似乎是让二维 vector 的第一个维度成为第一个点的标识，所有第二个点都存储在第二个维度中。

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

这不会打印被迭代的第一个维度的值。这将打印第二个维度的第一个值。这就是您得到重复输出的原因。

it 是包含第一个点的标识的 vector 的随机访问迭代器。如果是这样，

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

将对其索引进行逆向工程。但这太令人困惑了。

在外部使用索引迭代，在内部使用范围迭代来重写整个东西会更直接:

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

     for (auto j: adj[i])
        cout << j << "inside" << endl;
}