Daniel - 5 months ago 11

C++ Question

I'm building a graph in c++ as a vector of integer vectors

`vector<vector<int> > graph;`

my problem is:

- the graph is bidirectional, that means

`if G[u] contains v, G[v] contains u`

- I need to be able to

`remove any element v from G[u]`

remove u from G[v]

in constant time.

And this removal is an operation I'm gonna be repeating a lot, so a single map won't work, cause when I remove an element, the other elements would come one index back.

I'd like to remove an edge (the last index of G[u], for example, so I could use pop_back and get O(1) ), and then remove the corresponding edge in the other vertex' adjacence vector (

Answer

Use `unordered_set`

, the hash-based set, for the internal data structure.

That is, instead of

```
vector<vector<int> > graph;
```

use

```
vector<unordered_set<int>> graph;
```

To find if there is an edge from *u* to *v*:

```
graph[u].find(v) != graph[u].end();
```

If there is such an edge, then to remove it:

```
graph[u].erase(v);
```

All these operations are expected *O(1)*.