You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
60 lines
1.0 KiB
60 lines
1.0 KiB
// https://blog.51cto.com/u_3044148/5225981
|
|
|
|
/*
|
|
输入样例
|
|
3 3
|
|
1 2
|
|
1 3
|
|
2 3
|
|
3 2
|
|
1 2
|
|
2 3
|
|
0
|
|
|
|
输出样例
|
|
1
|
|
0
|
|
*/
|
|
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
const int N = 1010;
|
|
|
|
int n, m;
|
|
int p[N];
|
|
int d[N];
|
|
|
|
int find(int x) {
|
|
if (p[x] != x) p[x] = find(p[x]);
|
|
return p[x];
|
|
}
|
|
|
|
int main() {
|
|
#ifndef ONLINE_JUDGE
|
|
freopen("HDU1878.in", "r", stdin);
|
|
#endif
|
|
while (~scanf("%d%d", &n, &m) && n) {
|
|
memset(d, 0, sizeof d);
|
|
for (int i = 1; i <= n; i++) p[i] = i;
|
|
|
|
while (m--) {
|
|
int a, b;
|
|
scanf("%d%d", &a, &b);
|
|
d[a]++, d[b]++;
|
|
p[find(a)] = find(b);
|
|
}
|
|
|
|
int cnt = 0;
|
|
for (int i = 1; i <= n; i++)
|
|
if (p[i] == i) cnt++;
|
|
|
|
int odd = 0;
|
|
for (int i = 1; i <= n; i++)
|
|
if (d[i] & 1) odd++;
|
|
|
|
if (cnt == 1 && odd == 0)
|
|
puts("1"); // 连通并且没有奇度点
|
|
else
|
|
puts("0");
|
|
}
|
|
return 0;
|
|
} |