Generate Connected Graph

#include "testlib.h"
#include <vector>
#include <unordered_set>

std::vector<int> P;

int Root(int X) {
	return X == P[X] ? X : P[X] = Root(P[X]);
}

void GenConnectedGraph(int N, int M, std::vector<std::pair<int, int> > &R) {

	if (N < 1 || M + 1 < N || M > (long long)N * (N - 1) / 2) return;

	P.resize(N);
	for (int i = 0; i < N; i++) P[i] = i;

	std::unordered_set<long long> S;

	R.resize(M);
	for (int i = 0; i < N - 1; i++) {
		int u, v;
		do {
			u = rnd.next(N);
			v = rnd.next(N);
		} while (Root(u) == Root(v));
		P[Root(u)] = Root(v);
		R[i].first = u;
		R[i].second = v;
		S.insert((long long)u << 32 | v);
	}

	for (int i = N - 1; i < M; i++) {
		int u, v;
		do {
			u = rnd.next(N);
			v = rnd.next(N);
		} while (u == v || S.find((long long)u << 32 | v) != S.end() || S.find((long long)v << 32 | u) != S.end());
		R[i].first = u;
		R[i].second = v;
		S.insert((long long)u << 32 | v);
	}

	shuffle(R.begin(), R.end());
}

int main(int argc, char *argv[]) {
	registerGen(argc, argv, 1);

	int N = 7;
	int M = 10;

	std::vector<std::pair<int, int> > E;
	GenConnectedGraph(N, M, E);

	printf("%d %d\n", N, M);
	for (int i = 0; i < M; i++) printf("%d %d\n", E[i].first, E[i].second);

	return 0;
}