首页 > 代码库 > UVA11387 - The 3-Regular Graph(推理)
UVA11387 - The 3-Regular Graph(推理)
题目链接
题意:给n个点,问是否能画出一个无向图,且每个顶点连接3条边,如果可以的话输出连接的边。
思路:当增加一条边时,总的无向图的度数会增加2,所以度数之和n*2为偶数。当n为奇数时,度数之和为奇数,所以不存在。当n为偶数时才符合条件。注意特判n为2时的情况。输出的话,就头尾相连,然后i与i+(n/2)相连。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int const MAXN = 105; int n; void outPut() { printf("%d\n", n * 3 / 2); for (int i = 1; i <= n; i++) { int a = i; int b = i + 1; if (b > n) b %= n; printf("%d %d\n", a, b); } for (int i = 1; i <= n / 2; i++) printf("%d %d\n", i, i + (n / 2)); } int main() { while (scanf("%d", &n) && n) { if (n < 4 || n % 2) printf("Impossible\n"); else outPut(); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。