Codeforces Round #306 Div2 D: Regular Bridge

問題

Problem - D - Codeforces

各頂点からk本ずつ辺が出ているような無向グラフで、橋が存在するものは存在するか。

解法

k=1の時はサンプルをコピペする。

橋を取り除いた時、残ったグラフの片方は次数がk-1の頂点が1つ存在し、残りの頂点の次数はkである。この部分グラフの頂点の数をnとすると、辺の数は((n-1)*k+k-1)/2=(n*k-1)/2となる。これは整数でなければならないので、kが偶数の時は条件を満たすグラフは存在しない。

kが奇数の時、(n*k-1)/2が整数になるため、nも奇数であることが分かる。各頂点の次数はkまたはk-1なのでn>kでなければならないため、ひとまずn=k+2とする。

k+2角形（n角形）をつくり、対角線を引くと、全ての頂点の次数がk+1になるので、そこから、頂点1と頂点2を結ぶ辺、頂点3と頂点4を結ぶ辺、頂点5と頂点6を結ぶ辺、...、頂点k-2と頂点k-1を結ぶ辺、を取り除くと、頂点k、頂点k+1、頂点k+2の3つの頂点の次数がk+1、残りの頂点の次数がkになる。そこから頂点kと頂点k+2を結ぶ辺、頂点k+1と頂点k+2を結ぶ辺を取り除くと、頂点k+2の次数だけk-1、残りの次数がkになる。

この部分グラフを2つ作り、次数がk-1の頂点同士を結ぶと、条件を満たすグラフが完成する。

コード

import java.util.Scanner;
import java.util.TreeSet;

public class Main {
	private final int INF = 10000000;

	public void solve() {
		Scanner sc = new Scanner(System.in);
		int k = sc.nextInt();
		sc.close();

		if (k % 2 == 0) {
			System.out.println("NO");
			return;
		}
		if (k == 1) {
			System.out.println("YES");
			System.out.println("2 1");
			System.out.println("1 2");
			return;
		}
		System.out.println("YES");
		System.out.println(((k + 2) * 2) + " " + (k * k + 2 * k));
		TreeSet<Integer> set = new TreeSet<Integer>();
		for (int i = 1; i <= k + 1; i++) {
			for (int j = i + 1; j <= k + 2; j++) {
				set.add(i * INF + j);
				set.add((i + k + 2) * INF + (j + k + 2));
			}
		}
		for (int i = 1; i * 2 < k; i++) {
			set.remove((i * 2 - 1) * INF + (i * 2));
			set.remove((i * 2 - 1 + k + 2) * INF + (i * 2 + k + 2));
		}
		set.remove(k * INF + (k + 2));
		set.remove((k + 1) * INF + (k + 2));
		set.remove((2 * k + 2) * INF + (2 * k + 4));
		set.remove((2 * k + 3) * INF + (2 * k + 4));
		for (Integer integer : set) {
			int a = integer / INF;
			int b = integer % INF;
			System.out.println(a + " " + b);
		}
		System.out.println((k + 2) + " " + (2 * k + 4));
	}

	public static void main(String[] args) {
		new Main().solve();
	}

}