cubelover의 블로그

Generate Connected Graph

DM2016. 11. 7. 02:03
#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;
}

'DM' 카테고리의 다른 글

Generate Tree  (0) 2016.11.07
Testlib  (0) 2016.11.07

Generate Tree

DM2016. 11. 7. 01:35
#include "testlib.h"
#include <vector>

std::vector<int> P;

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

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

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

	M.resize(N - 1);
	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);
		M[i].first = u;
		M[i].second = v;
	}
}

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

	int N = 7;

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

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

	return 0;
}

'DM' 카테고리의 다른 글

Generate Connected Graph  (0) 2016.11.07
Testlib  (0) 2016.11.07

Testlib

DM2016. 11. 7. 01:08

Testlib는 Codeforces에서 만든 라이브러리이다.


Generator, Validator, Interactor 그리고 Checker를 만드는 데 사용할 수 있으며, C++ 표준을 따르는 어떤 컴파일러에서 실행시켜도 동일한 결과를 내놓으므로 컴파일러마다 작동이 다른 stdlib의 rand 함수로 만드는 것보다 데이터를 유지보수하기 좋다.


~


GitHub


Testlib를 사용하려면 공식 GitHub에 들아가서 testlib.h 파일을 클릭한 뒤, 소스를 복사하거나 Raw 버튼을 클릭하여 저장하면 된다. 이후 소스 파일과 같은 폴더에 넣은 뒤, 소스코드의 가장 앞 부분에 #include "testlib.h" 한 줄만 적어주면 Testlib를 사용할 수 있다.


~


Microsoft Visual Studio 2015


Microsoft Visual Studio 2015에서 Testlib를 사용하려고 하면 에러가 두 개 발생한다. (Testlib 0.9.10)


첫 번째 에러는 426번째 줄에서 발생하는 에러로, 407줄~409줄에 있는 다음 부분을 주석처리하면 해결된다.


/*
#ifndef _fileno
#define _fileno(_stream)  ((_stream)->_file)
#endif
*/


두 번째 에러는 va_start와 관련해서 발생하는 에러인데, testlib.h의 가장 앞 부분에 다음을 추가하면 해결된다.


#define _CRT_NO_VA_START_VALIDATION


이 두 가지를 해결하면 Microsoft Visual Studio 2015에서 Testlib를 사용할 수 있다.


~


Generator


generator에서 쓸 수 있는 다양한 함수들이 존재하므로, 직접 testlib.h 파일의 함수들을 하나씩 보거나 많은 예제를 찾아보면서 익히는 것을 권장한다.


아래는 길이가 1 이상 argv[1] 이하인 무작위 수열을 생성하는 generator의 예시이다.


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

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

	int MaxN = atoi(argv[1]);

	int N = rnd.next(1, MaxN);

	std::vector<int> A(N);

	for (int i = 0; i < N; i++) A[i] = i + 1;

	shuffle(A.begin(), A.end());

	printf("%d\n", N);
	for (int i = 0; i < N; i++) {
		if (i) printf(" ");
		printf("%d", A[i]);
	}
	printf("\n");

	return 0;
}


Testlib로 만든 generator는 맨 처음에 registerGen(argc, argv, 1)을 실행해야 한다. 이를 실행하면 인자로 넘어온 값들을 시드로 하여 랜덤함수를 초기화한다. 이 덕분에 generator를 실행할 때 인자를 바꿔주는 것만으로 같은 방법으로 생성된 서로 다른 데이터를 쉽게 만들 수 있다.

'DM' 카테고리의 다른 글

Generate Connected Graph  (0) 2016.11.07
Generate Tree  (0) 2016.11.07