UVA 11387 - The 3-Regular Graph（構造問題+推理證明）

I I U C O N L I N E C O N T E S T 2 0 0 8

Problem C: The 3-Regular Graph

Input: standard input

Output: standard output

The degree of a vertex in a graph is the number of edges adjacent to the vertex. A graph is 3-regular if all of its vertices have degree 3. Given an integer n, you are to build a simple undirected 3-regular graph with n vertices. If there are multiple solutions, any one will do.

Input

For each test case, the input will be a single integer n as described above. End of input will be denoted by a case where n = 0. This case should not be processed.

Output

If it is possible to build a simple undirected 3-regular graph with n vertices, print a line with an integer e which is the number of edges in your graph. Each of the following e lines describes an edge of the graph. An edge description contains two integers a & b, the two endpoints of the edge. Note that the vertices are indexed from 1 to n. If it is not possible to build a simple undirected 3-regular graph with n vertices, printImpossible in a single line.

Constraints

- 1 ≤ n ≤ 100

Sample Input

Output for Sample Input

4

3

0

6

1 2

1 3

1 4

2 3

2 4

3 4

Impossible

題意：給定n個點，要求用n個點構造出一個圖，每個頂點度數為3，問構造方法。

思路：構造問題，n為奇數是不行的，因為加一條邊度數+2，n*3為奇數，肯定不滿足，所以只有n為偶數可以，構造方式為，首尾連成圈，這樣度數為2了，然後在對角線全相連，度數為3，注意特判2的情況。

代碼：

#include 
#include 

int n;

void solve() {
	if (n < 3 || n % 2) printf("Impossible\n");
	else { 
		int i; printf("%d\n", n + n / 2);
		for (i = 1; i < n; i++)
			printf("%d %d\n", i, i + 1);
		printf("%d 1\n", n);
		for (i = 1; i <= n / 2; i++)
			printf("%d %d\n", i, i + n / 2);
	}
}

int main() {
	while (~scanf("%d", &n) && n) {
		solve();
	}
	return 0;
}