题目链接
/*
模板题-------判断欧拉回路
欧拉路径，无向图
1判断是否为连通图，
2判断奇点的个数为0
*/
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
using namespace std;
struct DisjoinSet {//并查集判断是否连通
vector<int> father, rank;
DisjoinSet(int n): father(n), rank(n) {
for (int i=; i<n; i++) {
father[i] = i;
}
}
int easy_find(int v) {//非递归
int k, j, r;
r = v;
while (r!=father[r]) {
r = father[r];
}
k = v;
while (k!=r) {
j = father[k];
father[k] = r;
k = j;
}
return r;
}
void merge(int x, int y) {
int a = easy_find(x), b = easy_find(y);
if (rank[a] < rank[b]) {
father[a] = b;
} else {
father[b] = a;
if (rank[b] == rank[a]) {
++rank[a];
}
}
}
} ;
const int MAXN = ;
int edge[MAXN];
int p, q;
int main()
{
// freopen("in.txt", "r", stdin);
while (~scanf("%d %d", &p, &q) && p) {
memset(edge, , sizeof(edge));
DisjoinSet mfs();
for (int i=; i<q; i++) {
int a, b;
scanf("%d %d", &a, &b);
edge[a]++;
edge[b]++;
mfs.merge(a, b);
}
int father = mfs.easy_find();
int ct = ;
for (int i=; i<=p; i++) {
if (mfs.father[i] != father) {
ct = -;
break;
}
if (edge[i] & ) ct++;
}
if (ct == ) printf("1\n");//欧拉回路
else printf("0\n");
}
return ;
}