D - 歐拉回路
HDU - 1878
歐拉回路是指不令筆離開紙面次企，可畫過圖中每條邊僅一次入桂，且可以回到起點(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
解法：并查集崔赌，如果一共只有一個(gè)集合意蛀，而且每個(gè)結(jié)點(diǎn)的度為偶數(shù)則為歐拉回路
代碼：
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
int degree[1005],pre[1005],cnt;
void init(int n){
memset(degree,0,sizeof(degree));
for(int i=0;i<n;i++)
pre[i]=i;
}
int root(int x){
if(x!=pre[x])
pre[x]=root(pre[x]);
return pre[x];
}
void insert(int a,int b){
int pa=root(a);
int pb=root(b);
if(pa!=pb){
cnt++;
pre[pa]=pb;
}
}
int main()
{
int n,m;
int x,y;
while(scanf("%d",&n)&&n){
init(n);
cnt=0;
scanf("%d",&m);
for(int i=0;i<m;i++){
scanf("%d%d",&x,&y);
degree[x]++;
degree[y]++;
insert(x,y);
}
if(cnt!=n-1){
cout<<0<<endl;
continue;
}
int flag=1;
for(int i=0;i<n;i++)
if(degree[i]%2){
flag=0;
break;
}
cout<<flag<<endl;
}
return 0;
}
