950
九度題目1027：歐拉回路
題目1027：歐拉回路時間限製：1 秒內存限製：32 兆特殊判題：否提交：2344解決：1157
題目描述：
歐拉回路是指不令筆離開紙麵，可畫過圖中每條邊僅一次，且可以回到起點的一條回路。現給定一個圖，問是否存在歐拉回路？
輸入：
測試輸入包含若幹測試用例。每個測試用例的第1行給出兩個正整數，分別是節點數N ( 1 < N < 1000 )和邊數M；隨後的M行對應M條邊，每行給出一對正整數，分別是該條邊直接連通的兩個節點的編號（節點從1到N編號）。當N為0時輸入結束。
輸出：
每個測試用例的輸出占一行，若歐拉回路存在則輸出1，否則輸出0。
樣例輸入：
3 3
1 2
1 3
2 3
3 2
1 2
2 3
0
樣例輸出：
1
0
來源：
2008年浙江大學計算機及軟件工程研究生機試真題
典型的歐拉回路
AC代碼：
#include<stdio.h>
#include<string.h>
struct node//創建一個路徑計數結構體
{
int len;
int path[1200];
}a[1200];
int jar[1200];
void DFS(int n)
{
int last;
while(a[n].len!=0)//深入搜索 a[n]每一個能連接的點
{
last=a[n].path[a[n].len-1];//傳回最後一個數據
jar[last]=1;//標記此路徑已經被聯通
a[n].len--;//刪除最後一個數據
DFS(last);//跳向下一個點進行搜索
}
}
int main()
{
int i,j,n,m,x,y,num,size,flag;
while(scanf("%d",&n),n!=0)
{
scanf("%d",&m);
memset(a,0,sizeof(a));
for(i=0;i<m;i++)
{
scanf("%d %d",&x,&y);
a[x].path[a[x].len++]=y;//a[x]末尾添加y
a[y].path[a[y].len++]=x;//a[y]末尾添加x
}
num=0;
for(i=1;i<=n;i++)
{
size=a[i].len;
if(size%2!=0)//檢查每一個點相對於其它點的連通性
num++;
}
memset(jar,0,sizeof(jar));
jar[1]=1;//先標記第一個點直接能通過
DFS(1);
flag=1;
for(i=1;i<=n;i++)//存在點一個點，其與任意一點都不相連
if(jar[i]==0)
{
flag=0;
break;
}
if(num!=0) flag=0;//等於0時是完全環，符合一筆畫，否則不是
if(flag==1)
printf("1\n");
else
printf("0\n");
}
return 0;
}
最後更新：2017-04-03 12:56:39