|
II U C ONLINE C ON TEST 2 008 |
|
|
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, print Impossible 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 |
|
|
|
|
Problem setter: Manzurur Rahman Khan Original idea: Mohammad Mahmudur Rahman |
|
时隔好几个月再写题解了。。。
题意：就是给出N个点，然后在这N个点间连线，使得每个点的度数为三，并输出每条线连接哪两个点。
思路：由图论知识可得，一条线意味着总度数加2，于是可得无论多少条线，总度数肯定为偶数，若给出奇数个点，3乘以一个奇数，恒为奇数，所以排除奇数个点的情况
然后偶数个点，首先收尾相连，然后每个点都是和对面的那个点相连即可。
AC代码：
#include<stdio.h>
int map[105][105];
int main() {
int n;
while(scanf("%d", &n) != EOF) {
if(n == 0)
break;
if(n % 2 == 1 || n == 2) {
printf("Impossible\n");
}
else if(n == 0)
break;
else {
int v = n + n / 2;
printf("%d\n", v);
for(int i = 1; i < n; i++)
printf("%d %d\n", i, i+1);
printf("%d 1\n", n);
for(int i = 1; i <= n/2; i++)
printf("%d %d\n", i, i+n/2);
}
}
return 0;
}UVA 11387 (14.2.28),布布扣,bubuko.com
原文：http://blog.csdn.net/qq297060023/article/details/20154379