Need a faster way to create an adjacency list in c++

user_17512096 0
Viewed 91

I'm trying to create an adjacency list from an input of vertices, edges and single connections. The input looks like this:

3 2 (vertices, edges)

1 2 (connection)

1 3

Right now, my code is

int vertices, edges;
scanf("%d %d", &vertices, &edges);

vector<vector<int>> storage[vertices+1];
for (int i = 0; i < edges; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    if (find(storage[b].begin(), storage[b].end(), a) != storage[b].end() == false) {
        storage[b].push_back(a);
    }
    if (find(storage[a].begin(), storage[a].end(), b) != storage[a].end() == false) {
        storage[a].push_back(b);
    }
}

Is there a faster/more efficient way to do this, or is this the best way?

adjacency-list arrays c++
1 Answers

It's nearly impossible to give a general answer to this kind of question, because the execution time is going to depend on factors that may be orders of magnitude apart. For instance, it could be that the cost of populating the data structure is insignificant compared to what you do with it afterwards. See also this answer, whose final recommendation I'll quote:

As always, profiling and measuring runtime and memory to find bottlenecks for you actual problem implementation is key if you are implementing a highperf computation program.

That answer also mentions some different STL containers you could consider. Here and here are two more questions on this topic.

With that said, measure before trying to improve anything. If reading the input piecewise turns out to be a bottleneck, for example, you could consider reading it all into a std::string in one go before further processing.

For completeness, I might write your current code in standard C++ like this:

#include <algorithm>
#include <iostream>
#include <vector>

// ...

// Speeds up std i/o, but don't mix the C and C++ interfaces afterwards
std::ios_base::sync_with_stdio(false);

int vertices, edges;
std::cin >> vertices >> edges;

std::vector<std::vector<int>> storage(vertices + 1);
// When filling vectors with push_back/emplace_back, it's best to call 
// reserve first. If using 1-based indexing, skip the first vector:
for (auto v = std::next(storage.begin()); v != storage.end(); ++v)
    v->reserve(vertices - 1);

// With C++20 support you can #include <ranges> and write
for (auto& v : storage | std::views::drop(1))
    v.reserve(vertices - 1);

auto found = [](auto const& vector, auto value) {
    return std::find(vector.begin(), vector.end(), value) != vector.end();
// or, with C++20: std::ranges::find(vector, value) != vector.end()
};

for (int a, b, i = 0; i < edges && std::cin >> a >> b; ++i) {
    if (!found(storage[b], a))
        storage[b].push_back(a);
    // ...
}
user_17199260
Related