sooo?

If you know beforehand approximately how much space you need, you can probably call std::vector::reserve

Probably not the most useful idea, however does emplace_back work?

Mushrooms function works in sqrt(x)/2

For the vectors, the fastest way is to use something similar to bucket sort, which is to merge all vectors into one array.

My vector filled copy paste code for SCCs ACd in around half of the TL, so that probably isn't the cause unless there's some compiler specific wizardry going on. I'm pretty sure the comment above hit the spot: the mushrooms function is the cause.

Try to use a different way to store the graph.

Example of directed graph:

// n is vertex count
// m is edge count
int U[100005],V[100005],head[100005],to[100005];
void graph_init(){
	for(int i=1;i<=m;++i) scanf("%d",&U[i]),scanf("%d",&V[i]);
	for(int i=1;i<=m;++i) ++head[U[i]];
	for(int i=head[0]=1;i<=n;++i) head[i]+=head[i-1];
	for(int i=1;i<=m;++i) to[--head[U[i]]]=V[i];
	head[n+1]=m+1;
}

iterate over all edges from vertex v:

for(int e=head[v];e<head[v+1];++e){
	int u=to[e];
	// e is edge id
	// an edge from v to u
	// ...
}