pair 和 vector 在 Graph 实现中如何工作？

Question

我似乎无法理解这段代码是如何使用 adj[i].push_back 格式来推送元素的，因为我创建了一个 1D 矢量，因此推送到一个元素不应该工作（问题 1）。并且在（问题 2）上，此代码使用类似于 2D 向量的向量并通过它输出。这是一个工作代码。我正在努力解决 hacker earth 上的一个问题。并发现这是最佳提交。

vector STL的功能我都分析过了。还是找不到答案。检查我是否可以在使用 v[i].push_back 声明一维向量后创建二维向量，它给我一个错误。检查了有关图实现的各种教程 none 似乎如何解决这实际上是如何工作的...

vector<pair<int,int>>adj[1001];
int values[100001];
int n,m,k,x,y;
cin>>n>>m>>k;
for(int i=0;i<n;i++)
{
    cin>>values[i];
}
for(int i=0;i<m;i++)
{
    cin>>x>>y;
    adj[x-1].push_back({values[y-1],y-1}); //problem-1
    adj[y-1].push_back({values[x-1],x-1});
}
for(int i=0;i<n;i++)
{
    sort(adj[i].begin(),adj[i].end());
}
int adj_size=0;
for(int i=0;i<n;i++)
{
    adj_size=adj[i].size();
    if(k>adj_size)
        cout<<-1<<"\n";
    else
        cout<<(adj[i][adj_size-k].second)+1<<"\n"; //problem-2
}

我只需要知道这些数据实际上是如何存储在向量中的。

Answer 1

我们一步步来看：

vector<pair<int,int>>adj[1001];

正在创建大小为 1001 的矢量数组。这相当于每个顶点都有list of edges，邻接表的基本概念。

这里用pair是因为邻接表要根据值排序，如果值相同，就要考虑索引

int values[100001];
int n,m,k,x,y;
cin>>n>>m>>k;
for(int i=0;i<n;i++)
{
    cin>>values[i];
}

以上代码从标准输入中获取值。

for(int i=0;i<m;i++)
{
    cin>>x>>y;
    adj[x-1].push_back({values[y-1],y-1}); //problem-1
    adj[y-1].push_back({values[x-1],x-1});
}

在这里，您正在制作一个无向图，其中 x 有一条边到 y，反之亦然。

for(int i=0;i<n;i++)
{
    sort(adj[i].begin(),adj[i].end());
}

按值的升序对每个邻接表进行排序。如果值相同，则比较索引

int adj_size=0;
for(int i=0;i<n;i++)
{
    adj_size=adj[i].size();
    if(k>adj_size)
        cout<<-1<<"\n";
    else
        cout<<(adj[i][adj_size-k].second)+1<<"\n"; //problem-2
}

Return 邻接表末尾的第 k 个元素（如果存在）。否则，return -1.

观察：

我认为如果值相同，此代码可能会失败。

相反，您应该在 sort 中定义自定义比较器。

像这样：

sort(adj[i].begin(),adj[i].end(), [](const pair<int, int> &p1, const pair<int, int> &p2) {
    if (p1.first != p2.first) {
        return p1.first > p2.first;
    }

    return p1.second < p2.second;
});

并且 return 从头开始的第 k 个元素。

建议:

我认为您应该使用 Maxheap，而不是使用这种方法。

pair 和 vector 在 Graph 实现中如何工作？

How does pair and vector work in Graph implementation?

c++

graph-algorithm