杭电ACM1878――欧拉回路
来源：程序员人生 发布时间：2015-08-06 10:24:49 阅读次数：3317次
简单的欧拉回路，如题。
欧拉回路的判断：
1.在有向图中：首先必要的条件是图连通，所以顶点的入度都等于出度。
2.在无向图中：重要条件还是图连通，其次就是所以顶点都是偶数度（该顶点的度为偶数）
这1题是无向图，所以根据判断方法来写，很简单，判定就不证明了。
我是用并查集来判断图是不是连通的。
下面是AC的代码：
#include <iostream>
#include <cstring>
using namespace std;
int par[1005], degree[1005];
int finds(int x)
{
if(x == par[x])
return x;
else
return par[x] = finds(par[x]);
}
int main()
{
int a, b, n, m, i;
while(cin >> n)
{
if(n == 0)
break;
for(i = 0; i <= n; i++)
par[i] = i;
memset(degree, 0, sizeof(degree));
cin >> m;
for(i = 0; i < m; i++)
{
cin >> a >> b;
degree[a]++; //该点度+1
degree[b]++;
int x = finds(a);
int y = finds(b);
if(x != y) //合并
par[x] = y;
}
int flag = 0, tag = 0;
for(i = 1; i <= n; i++) //判是不是连通
if(par[i] == i)
flag++;
if(flag > 1)
cout << 0 << endl;
else
{
for(i = 1; i <= n; i++) //判顶点的度是不是为偶数
{
if(degree[i] % 2)
tag++;
}
if(tag > 0)
cout << 0 << endl;
else
cout << 1 << endl;
}
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
