SDUT-3364_歐拉回路

數據結構實驗之圖論八：歐拉回路

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

在哥尼斯堡的一個公園里，有七座橋將普雷格爾河中兩個島及島與河岸連接起來。

能否走過這樣的七座橋，并且每橋只走一次？瑞士數學家歐拉最終解決了這個問題并由此創立了拓撲學。歐拉通過對七橋問題的研究，不僅圓滿地回答了哥尼斯堡七橋問題，并證明了更為廣泛的有關一筆畫的三條結論，人們通常稱之為歐拉定理。對于一個連通圖，通常把從某結點出發一筆畫成所經過的路線叫做歐拉路。人們又通常把一筆畫成回到出發點的歐拉路叫做歐拉回路。具有歐拉回路的圖叫做歐拉圖。

你的任務是：對于給定的一組無向圖數據，判斷其是否成其為歐拉圖？

Input

連續T組數據輸入，每組數據第一行給出兩個正整數，分別表示結點數目N(1 < N <= 1000)和邊數M；隨后M行對應M條邊，每行給出兩個正整數，分別表示該邊連通的兩個結點的編號，結點從1～N編號。

Output

若為歐拉圖輸出1，否則輸出0。

Sample Input

1
6 10
1 2
2 3
3 1
4 5
5 6
6 4
1 4
1 6
3 4
3 6

Sample Output

1

Hint

如果無向圖連通并且所有結點的度都是偶數，則存在歐拉回路，否則不存在。

題解：已經給了歐拉回路的判定條件，判定一下圖是否連通，然后就可以判斷一下是不是歐拉回路就可以了。

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>int n;/*n節點數量*/
int f[1050];/*記錄點是否被遍歷過*/
int INF = 1e9+7;/*相當于無窮大*/
int s[1050][1050];
int num[1050];/*記錄節點的度*/void DFS(int x)
{f[x] = 1;int i;for(i=1;i<=n;i++){if(!f[i]&&s[x][i])DFS(i);}
}int main()
{int t;int m,i,j;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(i=1;i<=n;i++)for(j=1;j<=n;j++)s[i][j] = 0;for(i=1;i<=n;i++)num[i] = f[i] = 0;for(i=0;i<m;i++)/*輸入邊的時候順便把端點的度記錄*/{int a,b;scanf("%d%d",&a,&b);s[a][b] = s[b][a] = 1;num[a] ++;num[b] ++;}for(i=1;i<=n;i++)/*判斷度是否都是偶數*/{if(num[i]%2)break;}if(i!=n+1)/*說明有點的度不是偶數，證明不是歐拉回路*/{printf("0\n");continue;}int ff = 0;for(i=1;i<=n;i++)/*判斷圖是否連通*/{if(!f[i])/*未標記說明是一顆新的樹（圖），對他進行DFS*/{ff ++;/*記錄樹（圖）的數量*/DFS(i);}}if(ff>1)/*樹（圖）的數量不唯一，說明圖不連通*/{printf("0\n");continue;}printf("1\n");}return 0;
}