文章标题 CSU 1834: Oil（欧拉路径）

1834: Oil

链接 1834: Oil
题意：Mike的车会漏油，所以开车经过的路径会有一条油 的路径。现在给出油的所有路径，问这些“油路” 是否是Mike一个人走的。约定Mike除了起始点外不 能停在任意一点，但可以重复经过某一点。判断路 径是否是Mike一个人走的。
分析：油滴落的路径相当于一条无向边，那么所有的路径 组合在一起就构成了一幅无向图，题目相当于问是 否能够找到一条路径使得经过每一条边即把所有边 遍历一次。所以可以得到题目就是要我们在无向图中是否存在一条欧拉路径，而欧拉路径的条件是
1、是一个连通图
2、度为奇数的点为0个或者2个
所以通过以上的分析，我们可以先判断图是否联通的，判断连通性我用的是BFS，同样也可以用并查集，判断完连通性后就通过计算度为奇数的数目来得到是否存在一条欧拉路径。
代码：

#include 
#include 
#include 
#include 
#include  
#include 
using namespace std;
int n,k;
int mp[105][105];
int used[105];
int vis[105];
int du[105];
int bfs(int s){//判断连通性 queue <int> q;q.push(s);vis[s]=1;while (!q.empty()){int tmp=q.front();q.pop();for (int i=0;iif (!vis[i]&&mp[tmp][i]){vis[i]=1;q.push(i);}}}for (int i=0;iif (used[i]){//如果发现有出现过的点没有在联通块里说明不是连通图 if (vis[i]==0)return 0;}}return 1;
}
int main()
{int t;cin>>t;while (t--){cin>>n;cin>>k;memset(mp,0,sizeof (mp));memset(vis,0,sizeof (vis));memset(used,0,sizeof (used));memset(du,0,sizeof (du));int u,v,val;for (int i=0;icin>>u>>v>>val;if (val<=0)continue;mp[u][v]=val;mp[v][u]=val;used[u]=1;//判断这个点用过 used[v]=1;du[u]+=val;//加上度数 ，有几条边就加上多少度 du[v]+=val;}int judge;for (int i=0;iif (used[i]){judge=bfs(i);break;}}if (judge==0){printf ("no\n");}else {//如果是联通图的话再判断奇数度的数目 int cnt=0;for (int i=0;iif (used[i]){if (du[i]%2==1)cnt++;}}if (cnt==0||cnt==2)printf ("yes\n");else printf ("no\n");}}return 0;} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！