題意：給定n個(gè)點(diǎn)，然后構(gòu)造一個(gè)n個(gè)點(diǎn)的無(wú)向圖，每個(gè)點(diǎn)的度數(shù)為3；

思路：由圖論握手定理可知，每條邊都會(huì)連接2個(gè)點(diǎn)，那么點(diǎn)數(shù)應(yīng)為偶數(shù)個(gè)，奇數(shù)不可能，每個(gè)點(diǎn)為3度，那么有n*3/2條邊，然后依次連接相鄰的就可以了。

code：

#include <bits/stdc++.h> using namespace std;int main() {int n;while (~scanf("%d",&n),n){if (n%2||n==2) {puts("Impossible");continue;}printf("%d\n",n+n/2);for (int i=1;i<n;i++)printf("%d %d\n",i,i+1);printf("%d %d\n",1,n);for (int i=1;i<=n/2;i++)printf("%d %d\n",i,i+n/2);} }

總結(jié)

以上是生活随笔為你收集整理的uva 11387——The 3-Regular Graph的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。