南阳理工ACM42――一笔画问题
来源：程序员人生 发布时间：2015-05-13 08:22:24 阅读次数：2478次
1笔划问题，也就是欧拉道路，这1题，简单的欧拉回路的利用。
甚么是欧拉回路？
欧拉回路就是在图A中，存在1条路径使得每条边都走过1次，并且这条路径是1个圈，就是欧拉回路。
欧拉回路的判断：
1.在有向图中：首先必要的条件是图连通，所以顶点的入度都等于出度。
2.在无向图中：重要条件还是图连通，其次就是所以顶点都是偶数度（该顶点的度为偶数）
这1题，还需要加上1个条件，也就是存在两个奇数度的点的情况，也是符合的，从1个奇数点动身，另外1个奇数点结束。
判断图是不是连通，可以应用DFS或并查集，都是很简单的。
下面是dfs的算法：
void dfs(int x)
{
int i;
vis[x] = 1; //标记已返问过
for(i = 1; i <= n; i++)
if(map[x][i])
{
degree[x]++; //该点度+1
if(vis[i] == 0) //没返问过，递归
dfs(i);
}
}
下面是AC的代码，我用的是并查集来判连通：
#include <iostream>
#include <cstring>
using namespace std;
const int MAX_N = 1005;
int par[MAX_N], degree[MAX_N], n, v;
int finds(int x)
{
if(x == par[x])
return x;
else
return par[x] = finds(par[x]);
}
int main()
{
// freopen("data.txt", "r", stdin);
int t, a, b, i, j;
cin >> t;
while(t--)
{
cin >> n >> v;
memset(degree, 0, sizeof(degree));
for(j = 0; j <= n; j++) //初始化并查集
par[j] = j;
for(i = 0; i < v; i++)
{
cin >> a >> b;
degree[a]++; degree[b]++; //该点度+1
int next_a = finds(a);
int next_b = finds(b);
if(next_a != next_b) //合并
par[next_a] = next_b;
}
int flag = 0, tag = 0;
for(i = 1; i <= n; i++) //判连通
if(par[i] == i)
flag++;
if(flag > 1) //不连通
cout << "No" << endl;
else //连通
{
for(i = 1; i <= n; i++) //判奇数点
if(degree[i] % 2)
tag++;
if(tag == 0 || tag == 2)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
