I have never come across any slowness issues using an array of vectors.
But do use an array of vectors, not a vector of vectors. Usually you know the number of vertexes, so
vector<int> e[MAXIMUM_NO_OF_VERTICES]
should be sufficient, where e[v][i] is the ith vertex that v is connected to. It's also easier IMO than a vector of vectors.
Also, dense means that the number of edges is nearly the number of pairs of vertices, not number of vertexes.
A vertex with number of edges around the number of vertices is a very sparse graph.
An adjacency matrix is feasible only if N^2 is pretty small. For ~~N ~~number of vertexes around 10^5 the size of an adjacency matrix is 4*10^10 (around 40 GB) which is certainly not going to fit within any memory limit. In such cases you must use an adjacency list, which will fit in O(number of edges) memory space. Number of edges can be around 10^5, it still takes up only around 800 KB. (4 bytes per int * 2 vertices per edge * 100000 edges)