打印邻接表

Question

我刚从图表开始，用对向量和unordered_map打印邻接列表，不过当我根据随机的自定义输入测试代码时，它符合预期的结果，但当我将它提交给在线判断时，它给了我一个分割错误。

问题：

给定双向图的边'E‘和顶点'V’的个数。您的任务是通过邻接列表构建一个图，并打印每个顶点的邻接列表。

输入：

输入的第一行是T，表示每个T的第一行包含两个正整数V和E，其中'V‘是顶点数，'E’是图中的边数。接下来，'E‘线包含两个正数，表示这两个顶点之间有一个边。

输出：

对于每个顶点，打印它们所连接的节点，以便将它们推入列表中。

#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>
using namespace std;
int main()
 {
  int T;
  cin>>T;
  while(T--){
  int nv,ne;
  cin>>nv>>ne;
  vector<pair<int,int>> vect;
  for(int i=0;i<ne;i++)
{  int k,l;

    cin>>k>>l;vect.push_back( make_pair(k,l) );    
}
unordered_map<int,vector<int>> umap;
for(int i=0;i<ne;i++)
{
   umap[vect[i].first].push_back(vect[i].second);
    umap[vect[i].second].push_back(vect[i].first);
}
for(int i=0;i<nv;i++)
{
    sort(umap[i].begin(),umap[i].end());
}
int j=0;
for(int i=0;i<nv;i++)
{
   cout<<i<<"->"<<" ";
    for( j=0;j<umap[i].size()-1;j++)
    {
      cout<<umap[i][j]<<"->"<<" ";  
    }
    cout<<umap[i][j];
    cout<<"\n";
}
}
return 0;
}

示例：

输入：

1

5 7

0 1

0 4

1 2

1 3

1 4

2 3

3 4

输出：

0-> 1-> 4

1-> 0-> 2-> 3-> 4

2-> 1-> 3

3-> 1-> 2-> 4

4-> 0-> 1-> 3

Answer 1

当顶点没有边时，就会产生“分割错误”。在问题描述中，我没有看到所有顶点至少有一个边的约束。例如，让我们考虑这个输入。

1
3 1
0 1

这里顶点2没有任何边。让我们看看打印循环中发生了什么。

for(int i=0;i<nv;i++)
{
   cout<<i<<"->"<<" ";
    for( j=0;j<umap[i].size()-1;j++)
    {
      cout<<umap[i][j]<<"->"<<" ";  
    }
    cout<<umap[i][j];
    cout<<"\n";
}

1. umap[i].size()-1是危险的:因为vector<T>::size()返回一个无符号整数。因此，如果大小为0，则为0-1，这将导致底流。
2. 即使解决了第一个问题(类似于(int)umap[i].size()-1)，下面的行cout<<umap[i][j];也会尝试打印如果大小为0时无效的umap[i][0]

所以我会修改代码如下：

for(int i=0;i<nv;i++)
{
  cout<<i;
  for( j=0;j<umap[i].size();j++)
  {
    cout<<"->"<<" "<<umap[i][j];
  }
  cout<<"\n";
}