UVa 10596 - Morning Walk（无向图） 题意：在一个无向图中，每条边只能通过一次，问最终所有路都经过一次，能否回到起点！ 思路：1.注意这是个无向图，A到B有两条路的话，可以从A-B走两
UVa 10596 - Morning Walk（无向图）
题意：在一个无向图中，每条边只能通过一次，问最终所有路都经过一次，能否回到起点！
思路：1.注意这是个无向图，A到B有两条路的话，可以从A->B走两次；
没要求走完所有点，所以不必要整个图都连通，一个连通块也行，但不能有多个。
看几组特殊测试用例：
/**
2 0
Possible
10 2
8 9
9 8
Possible
10 4
2 4
4 2
8 9
9 8
Not Possible
*/
AC代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <stack>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
using namespace std;
#define LL long long
#define M 210
#define DEBUG puts("It's here!")
#define INF 1<<29
#define CLS(x,v) memset(x,v,sizeof(x))
#define FOR(i,a,n) for(int i=(a);i<(n);++i)
/**这是一个无向图，每条边只能走一次，
输入A到B可能有多条路, 求是否存在欧拉回路。
(每条边都要走一次仅且一次,如果能就possible)
有的点可以独立，不一定要整个图都联通，连通分量个数不大于1是可行的
*/
int gree[M];
int n;
int f[M];
int Find(int x)
{
if(x==f[x])return x;
f[x]=Find(f[x]);
return f[x];
}
bool check()
{
int cnt=0;
for(int i=0; i<n; i++)
if(gree[i]&&f[i]==i)
cnt++;
for(int i=0; i<n; i++)
{
if(gree[i]&1)return 0;
}
return 1;
}
int main()
{
int k,x,y,a,b;
while(~scanf("%d%d",&n,&k))
{
CLS(gree,0);
for(int i=0; i<n; i++)f[i]=i;
for(int i=0; i<k; i++)
{
scanf("%d%d",&x,&y);
gree[x]++;
gree[y]++;
a=Find(x);
b=Find(y);
f[a]=b;
}
if(check())printf("Possible\n");
else printf("Not Possible\n");
}
return 0;
}