歐拉回路

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 18525????Accepted Submission(s): 7193

Problem Description

歐拉回路是指不令筆離開紙面，可畫過圖中每條邊僅一次，且可以回到起點(diǎn)的一條回路。現(xiàn)給定一個(gè)圖，問是否存在歐拉回路？

Input

測(cè)試輸入包含若干測(cè)試用例。每個(gè)測(cè)試用例的第1行給出兩個(gè)正整數(shù)，分別是節(jié)點(diǎn)數(shù)N ( 1 < N < 1000 )和邊數(shù)M；隨后的M行對(duì)應(yīng)M條邊，每行給出一對(duì)正整數(shù)，分別是該條邊直接連通的兩個(gè)節(jié)點(diǎn)的編號(hào)（節(jié)點(diǎn)從1到N編號(hào)）。當(dāng)N為0時(shí)輸入結(jié)
束。

Output

每個(gè)測(cè)試用例的輸出占一行，若歐拉回路存在則輸出1，否則輸出0。

Sample Input

3 3 1 2 1 3 2 3 3 2 1 2 2 3 0

Sample Output

1 0

Source

浙大計(jì)算機(jī)研究生復(fù)試上機(jī)考試-2008年

Recommend

We have carefully selected several similar problems for you:??1879?1880?1877?1881?1863?

若圖G中存在這樣一條路徑，使得它恰通過G中每條邊一次,則稱該路徑為歐拉路徑。

若該路徑是一個(gè)圈，則稱為歐拉(Euler)回路。具有歐拉回路的圖為歐拉圖。

定理：

（一）一個(gè)圖有歐拉回路當(dāng)且僅當(dāng)它是連通的且每個(gè)頂點(diǎn)都有偶數(shù)度。

（二）一個(gè)圖有歐拉通路當(dāng)且經(jīng)當(dāng)它是連通的且除兩個(gè)頂點(diǎn)外，其他頂點(diǎn)都有偶數(shù)度。

在第二個(gè)定理下，含奇數(shù)度的兩個(gè)節(jié)點(diǎn)中，一個(gè)必為歐拉通路起點(diǎn)，另一個(gè)必為歐拉通路的終點(diǎn)。

1.判斷歐拉路是否存在的方法
有向圖：圖連通，有一個(gè)頂點(diǎn)：出度=入度+1，有一個(gè)頂點(diǎn)：入度=出度+1，其余都是出度=入度。
無向圖：圖連通，只有兩個(gè)頂點(diǎn)是奇數(shù)度，其余都是偶數(shù)度。

2.判斷歐拉回路是否存在的方法
有向圖：圖連通，所有的頂點(diǎn)出度=入度。
無向圖：圖連通，所有頂點(diǎn)都是偶數(shù)度。

用DFS判斷圖是否連通

#include<bits/stdc++.h> using namespace std; #define maxn 1005 #define inf 0x3f3f3f3f int n,m; vector<int> G[maxn]; bool vis[maxn];//標(biāo)記節(jié)點(diǎn)是否遍歷過 int degree[maxn];//記錄節(jié)點(diǎn)的度 void dfs(int point)//深度優(yōu)先搜索每個(gè)點(diǎn) {vis[point]=1;//標(biāo)記訪問過for(int i=0;i<G[point].size();i++)//遍歷所有與當(dāng)前點(diǎn)相鄰的點(diǎn){int next=G[point][i];if(!vis[next])//如果沒有訪問過dfs(next);//繼續(xù)訪問} } int main() {while(scanf("%d",&n)!=EOF&&n){scanf("%d",&m);for(int i=1;i<=n;i++)G[i].clear();//多組測(cè)試，一定要清空memset(vis,0,sizeof(vis));memset(degree,0,sizeof(degree));while(m--){int u,v;scanf("%d%d",&u,&v);degree[u]++;//節(jié)點(diǎn)度數(shù)+1degree[v]++;G[u].push_back(v);G[v].push_back(u);}dfs(1);bool flag=0;for(int i=1;i<=n;i++)if(!vis[i]){//如果存在節(jié)點(diǎn)沒有訪問過，則圖不連通flag=1;break;}if(flag)printf("0\n");else{flag=0;for(int j=1;j<=n;j++)if(degree[j]&1)//奇數(shù){//存在某個(gè)點(diǎn)的度數(shù)為奇數(shù)，則不是歐拉回路flag=1;break;}if(flag) printf("0\n");else printf("1\n");}}return 0; }

用并查集來判斷圖是否連通

#include<bits/stdc++.h> using namespace std; #define maxn 1005 #define inf 0x3f3f3f3f int n,m; int pre[maxn];//標(biāo)記每個(gè)節(jié)點(diǎn)的前驅(qū) int degree[maxn];//每個(gè)節(jié)點(diǎn)的度 int findset(int x)//尋找前驅(qū) {if(pre[x]==x)return x;return pre[x]=findset(pre[x]);//壓縮路徑 } void unionset(int x,int y)//合并兩個(gè)連通分量 {int fx=findset(x),fy=findset(y);pre[fx]=fy; } int main() {while(scanf("%d",&n)!=EOF&&n){scanf("%d",&m);for(int i=1;i<=n;i++)pre[i]=i;//初始化前驅(qū)為自己memset(vis,0,sizeof(vis));memset(degree,0,sizeof(degree));while(m--){int u,v;scanf("%d%d",&u,&v);degree[u]++;//度數(shù)+1degree[v]++;unionset(u,v);}bool flag=0;int father=findset(1);//根節(jié)點(diǎn)for(int i=2;i<=n;i++)if(findset(i)!=father){//存在其他根節(jié)點(diǎn)flag=1;break;//則圖是不連通的}if(flag)printf("0\n");else{flag=0;for(int j=1;j<=n;j++)if(degree[j]&1)//奇數(shù){flag=1;break;}if(flag) printf("0\n");else printf("1\n");}}return 0; }

?

總結(jié)

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

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