歐拉回路

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

Problem Description

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

Input

測試輸入包含若干測試用例。每個測試用例的第1行給出兩個正整數，分別是節點數N ( 1 < N < 1000 )和邊數M；隨后的M行對應M條邊，每行給出一對正整數，分別是該條邊直接連通的兩個節點的編號（節點從1到N編號）。當N為0時輸入結
束。

Output

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

Sample Input

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

Sample Output

1 0

Source

浙大計算機研究生復試上機考試-2008年

Recommend

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

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

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

定理：

（一）一個圖有歐拉回路當且僅當它是連通的且每個頂點都有偶數度。

（二）一個圖有歐拉通路當且經當它是連通的且除兩個頂點外，其他頂點都有偶數度。

在第二個定理下，含奇數度的兩個節點中，一個必為歐拉通路起點，另一個必為歐拉通路的終點。

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

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

用DFS判斷圖是否連通

#include<bits/stdc++.h> using namespace std; #define maxn 1005 #define inf 0x3f3f3f3f int n,m; vector<int> G[maxn]; bool vis[maxn];//標記節點是否遍歷過 int degree[maxn];//記錄節點的度 void dfs(int point)//深度優先搜索每個點 {vis[point]=1;//標記訪問過for(int i=0;i<G[point].size();i++)//遍歷所有與當前點相鄰的點{int next=G[point][i];if(!vis[next])//如果沒有訪問過dfs(next);//繼續訪問} } int main() {while(scanf("%d",&n)!=EOF&&n){scanf("%d",&m);for(int i=1;i<=n;i++)G[i].clear();//多組測試，一定要清空memset(vis,0,sizeof(vis));memset(degree,0,sizeof(degree));while(m--){int u,v;scanf("%d%d",&u,&v);degree[u]++;//節點度數+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]){//如果存在節點沒有訪問過，則圖不連通flag=1;break;}if(flag)printf("0\n");else{flag=0;for(int j=1;j<=n;j++)if(degree[j]&1)//奇數{//存在某個點的度數為奇數，則不是歐拉回路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];//標記每個節點的前驅 int degree[maxn];//每個節點的度 int findset(int x)//尋找前驅 {if(pre[x]==x)return x;return pre[x]=findset(pre[x]);//壓縮路徑 } void unionset(int x,int y)//合并兩個連通分量 {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;//初始化前驅為自己memset(vis,0,sizeof(vis));memset(degree,0,sizeof(degree));while(m--){int u,v;scanf("%d%d",&u,&v);degree[u]++;//度數+1degree[v]++;unionset(u,v);}bool flag=0;int father=findset(1);//根節點for(int i=2;i<=n;i++)if(findset(i)!=father){//存在其他根節點flag=1;break;//則圖是不連通的}if(flag)printf("0\n");else{flag=0;for(int j=1;j<=n;j++)if(degree[j]&1)//奇數{flag=1;break;}if(flag) printf("0\n");else printf("1\n");}}return 0; }

?

總結

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

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