UVa 10596: Morning Walk

本文主要是介绍UVa 10596: Morning Walk，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这题需要判断两个地方：所有点是否在同一个集合中以及各点的度是否均为偶数（即是否可以构成欧拉回路）。

用dfs得到一个连通分量中点的个数，判断是否与总的点数目相等即可知道是否所有点均在一个连通分量中。

我的代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <string>
#include <algorithm>
using namespace std;int degree[200];
int adj[200][200];
int visit[200];
int N,R;void dfs(int n, int &c)
{c++;visit[n]=1;for(int i=0; i<N; i++){if(adj[i][n] && !visit[i]){dfs(i,c);}}return ;
}int main()
{int ta,tb;while(cin >> N >> R){memset(adj,0,sizeof(adj));memset(degree,0,sizeof(degree));memset(visit,0,sizeof(visit));for(int i=0; i<R; i++){cin >> ta >> tb;adj[ta][tb]=adj[tb][ta]=1;degree[ta]++;degree[tb]++;}int ok=1,count=0;for(int i=0; i<N; i++){if(degree[i]%2==1) { ok=0; break;}}if(!ok) cout << "Not Possible\n";else {dfs(0,count); //cout << count << endl;if(count != N) cout << "Not Possible\n";else cout << "Possible\n";}}return 0;
}

这篇关于UVa 10596: Morning Walk的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---