What you need is to take advantage of disjoint set, a very efficient data structure.
Here is the simple algorithm to generate a random graph of $n$ vertices and $m$ component.
- MakeSet of size $n$.
- Choose two random vertices that has not been connected by an edge.
- Union these two vertices. That means adding the edge between them. Use an implementation of the union operation that tells you if two different components are unioned.
- Stop if the number of components become $m$. Go back to step 2 otherwise.
There are existing implementations of disjoint set in C/C++, Java, Python, or just about every popular language.
You can implement step 2 in various ways.
You can use rejection sampling. Choose two random vertices. Repeat if the edge between them has been added.
This method is about the simplest to implement. It is efficient when the number of components is greater than a fixed proportion of the number of vertices. It takes little time if the number of vertices is not large.
- You can also keep track of the degree of each vertex. Choose a vertex whose degree is not $n-1$. The choose an edge from that vertex.
You can vary step 3 as well. Step 3 above is aimed to produce a random graph with given number of components and the "minimal" number of edges.
- One way to get random number of edges is to continue adding some random number of random edges after step 3 as long as no two different components become unioned/connected.
- One way to get denser graphs is to not add the edge when it connects two different component with some probability $p$. The larger $p$ is, the more edges.
In the special case of one component (connected graph) and many vertices, you can also generate a random tree using Prüfer sequence, followed by adding some random edges.
As you have mentioned, you could also generate $m$ random connected graphs with given numbers of vertices, the joining them together. Each connected graph can be generated using either disjoint set or Prüfer sequence.
Note that for all above variations, the distribution of the generated graphs is probably different from each other. It is your task to choose an implementation whose randomness/biasness is what you want. Or roughly.