Как работает пара и вектор в реализации Graph? - PullRequest
Новая
       14

Как работает пара и вектор в реализации Graph?

0 голосов
/ 17 января 2019

Я не могу понять, как этот код использует формат adj [i] .push_back для проталкивания элементов, поскольку я создал 1D-вектор, поэтому вставка в элемент не должна работать (проблема-1) , А также (проблема-2) этот код использует вектор, такой как 2D-вектор, и выводит его через него. Это рабочий код. Я изо всех сил пытался решить проблему на хакерской земле. И нашел это как лучший представленный.

Я проанализировал все функции вектора STL. Все еще не мог найти ответ. Проверил, могу ли я создать 2D вектор после объявления 1D вектора с помощью v [i] .push_back. Это выдало ошибку. Проверил различные учебники по реализации графа, но ни один из них не рассматривает, как это на самом деле работает ... 

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
}

Мне просто нужно знать, как эти данные на самом деле хранятся в векторе.

1 Ответ

0 голосов
/ 17 января 2019

Давайте посмотрим на это шаг за шагом: 

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

Создание массива размером 1001 вектора. Это эквивалентно наличию list of edges для каждой вершины, базовой концепции списка смежности.

Здесь используется пара, поскольку список смежности должен быть отсортирован по значению, а если значение одинаково, то следует учитывать индекс. 

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
}

Возвращает k-й элемент из конца списка смежности, если он существует. В противном случае верните -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;
});

И вернуть k-й элемент с начала.

Предложение:

Вместо того, чтобы использовать этот подход, я думаю, вы должны пойти на Maxheap.

...