Description
输入n,构造一个n个点的无向图,使得每个点的度数都为3。不能有重边和自环,输出图或确定无解。
Solution
如果n为奇数,奇数*3=奇数,度数为奇,必无解。
考虑我们怎么构造一个图使得每个点度数为2?显然是直接连一个环。
再让他们度数为3,让点两两一连就行了。
秒之。
Code
注意n=2虽然是偶数但也无解。
#include<cstdio>
int main(){
int n;
while(scanf("%d",&n)==&&n){
if(n==||n%==){
printf("Impossible\n");
continue;
}
else{
printf("%d\n",n+n/);
for(int i=;i<n;i++)
printf("%d %d\n",i,i+);
printf("%d 1\n",n);
for(int i=;i<=n/;i++)
printf("%d %d\n",i,i+n/);
}
}
return ;
}