UTPC 2011 F: 全域木

問題概要

ノード数Nの完全グラフから、K種類の互いに辺を共有しない全域木を構成する問題。

解法

解説を参考にして実装した。円上にノードを配置してぐるぐる回すという方法で、様々な作り方があるらしい。

#include <cstdio>
using namespace std;

int N, K;

void solve(){
	for(int st=0; st<K; st++){
		int cur = 0;
		for(int i=0; i<N-1; i++){
			int next = (cur>N/2?N-cur:N-cur-1);
			printf("%d %d\n", (cur+st)%N+1, (next+st)%N+1);
			cur = next;
		}
		puts("");
	}
}

int main(){
	scanf("%d%d",&N,&K);
	if(K > N/2){
		puts("-1");
		return 0;
	}
	solve();
	return 0;
}