P1718 圖形復原

題目描述

HWX小朋友對幾何的熱愛在電腦組是出了名的，號稱“每題必解”，這天，LXC在玩logo的時候突然想到了一個題目，剛好可以去測試一下他封號的虛實，于是，他logo編程畫了一個n邊形，并且將n個頂點用1，2，3，…,n這n個連續自然數隨手編了個號，為了增加難度，他又畫了一些不相交的對角線。如下圖：

他把所有的邊和對角線都寫在一張紙上，對于上圖，他寫了：（1，3），（3，2），（2，4），（4，5），（5，1），（1，4），（3，4）。正得意的時候，電腦突然自動重啟了，郁悶的是，他忘記保存剛才的logo程序了，此刻的他很想利用紙上記錄的信息將這個n邊形的編號復原，電腦組的你能幫助他嗎？

輸入輸出格式

輸入格式：

?

第一行n（n<=50）

下面若干行，每行兩個數a，b，表示紙上記錄的信息。

?

輸出格式：

?

僅一行，按字典序較小的順序依次輸出頂點的編號。對于上面的例子，你的輸出應該是1 3 2 4 5。

?

輸入輸出樣例

輸入樣例#1：?復制 5 1 3 3 2 2 4 4 5 5 1 1 4 3 4 輸出樣例#1：?復制 1 3 2 4 5
思路：搜索。 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,m; int ans[60],vis[60],map[60][60]; bool dfs(int now,int tot){if(tot==n+1&&now==1) return true;for(int i=1;i<=n;i++)if(map[now][i]&&!vis[i]){vis[i]=1;map[now][i]=map[i][now]=0;ans[tot]=i;if(dfs(i,tot+1)) return true;vis[i]=0;map[now][i]=map[i][now]=1;}return false; } int main(){scanf("%d",&n);int a,b;while(scanf("%d%d",&a,&b)!=EOF)map[a][b]=map[b][a]=1;dfs(1,1);cout<<"1"<<" ";for(int i=1;i<n;i++)cout<<ans[i]<<" "; }

?

?

轉載于:https://www.cnblogs.com/cangT-Tlan/p/8017754.html

總結

以上是生活随笔為你收集整理的洛谷 P1718 图形复原的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。