HDU1878欧拉回路（连通图+度的判断）

欧拉回路是指不令笔离开纸面&＃xff0c;可画过图中每条边仅一次&＃xff0c;且可以回到起点的一条回路。现给定一个图&＃xff0c;问是否存在欧拉回路&＃xff1f;

Input

测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数&＃xff0c;分别是节点数N ( 1 束。

Output

每个测试用例的输出占一行&＃xff0c;若欧拉回路存在则输出1&＃xff0c;否则输出0。 

Sample Input

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

Sample Output

1
0

题解&＃xff1a;我们知道欧拉回路主要是有两个条件&＃xff1a;1.连通图 。2.所有点的度都为偶数。然后此题就可解了

代码如下&＃xff1a;

#include
#include
#include
#includeusing namespace std;
int pre[10005];
int find (int x)
{if(x&＃61;&＃61;pre[x])return x;else{return pre[x]&＃61;find(pre[x]);}
}
void merge(int x,int y)
{int fx&＃61;find(x);int fy&＃61;find(y);if(fx!&＃61;fy){pre[fx]&＃61;fy;}
}
bool connect(int n)
{int cnt&＃61;0;for(int t&＃61;1;t<&＃61;n;t&＃43;&＃43;){if(pre[t]&＃61;&＃61;t)cnt&＃43;&＃43;;}if(cnt&＃61;&＃61;1){return true;}else{return false;}}
int main()
{int n,m;int deg[100005];while(scanf("%d",&n)){if(n&＃61;&＃61;0){break;}scanf("%d",&m);for(int t&＃61;1;t<&＃61;n;t&＃43;&＃43;){pre[t]&＃61;t;}for(int t&＃61;1;t<&＃61;n;t&＃43;&＃43;){deg[t]&＃61;0;}int a,b;for(int t&＃61;0;t}