題目大意：有n個(gè)珠子，珠子兩邊的顏色已知，問(wèn)能否連成一條項(xiàng)鏈。（兩個(gè)珠子可以項(xiàng)鏈當(dāng)且僅當(dāng)一個(gè)珠子的一邊顏色與另一個(gè)珠子的另一邊顏色相同）。

題目分析：歐拉回路。將顏色視作節(jié)點(diǎn)，珠子當(dāng)做邊，問(wèn)題變成了找一條歐拉回路。

歐拉回路存在的條件：無(wú)向圖：1.圖連通；2.無(wú)奇點(diǎn)；　　有向圖：1.忽略邊的方向后，圖連通；2.每個(gè)點(diǎn)的入度都等于出度；

注意：輸出回路的時(shí)候要逆序輸出。。。

?

代碼如下：

# include<iostream> # include<cstdio> # include<vector> # include<cstring> # include<algorithm> using namespace std;int n,du[55],v[55][1005],mp[55][55],vis[55];void dfs(int u) {for(int i=1;i<=v[u][0];++i){int k=v[u][i];if(!vis[k]){vis[k]=1;dfs(k);}} }bool judge() {memset(vis,0,sizeof(vis));int cnt=0;for(int i=1;i<=50;++i){if(du[i]==0)continue;if(!vis[i]){++cnt;if(cnt>1)return false;vis[i]=1;dfs(i);}}for(int i=1;i<=50;++i)if(du[i]&1)return false;return true; }void print(int u) {for(int i=1;i<=v[u][0];++i){int k=v[u][i];if(!mp[u][k])continue;--mp[u][k],--mp[k][u];print(k);printf("%d %d\n",k,u);///逆序輸出} }int main() {int T,a,b,cas=0;scanf("%d",&T);while(T--){memset(du,0,sizeof(du));memset(mp,0,sizeof(mp));scanf("%d",&n);for(int i=0;i<55;++i)v[i][0]=0;while(n--){scanf("%d%d",&a,&b);v[a][++v[a][0]]=b;v[b][++v[b][0]]=a;++du[a],++du[b];++mp[a][b],++mp[b][a];}printf("Case #%d\n",++cas);if(!judge())printf("some beads may be lost\n");else{for(int i=1;i<=50;++i){if(du[i]>0){print(i);break;}}}if(T)printf("\n");}return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/20143605--pcx/p/4892882.html

總結(jié)

以上是生活随笔為你收集整理的UVA-10054 The Necklace （欧拉回路）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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