欧拉回路热门博客列表 - ITeye博客频道

博客专栏推荐

本月博客排行

年度博客排行

Play on Words 并查集加欧拉回路

//用并查集的时候先将当做无向图来处理判断图的连通性。 //然后用欧拉路的定义来求解。存在欧拉回路的条件是：所有点出度==入度。 //存在欧拉道路的条件是：有且仅有两个点出度！=入度，且出度和入度之差为1.其余点出度==入度 #include <stdio.h> #include <cstring> int f[27]; int in[27]; int out[27]; bo ...

欧拉回路

yingchifei 评论(0) 有4人浏览 2012-08-15 13:24

链接：http://poj.org/problem?id=2513 1.把木棒的端点考虑为顶点，木棒考虑为边，建立起一个无向图。 2.问题转化为在无向图上判断是否有欧拉回路或者欧拉道路。 3.在无向图上判断是否有欧拉回路或者欧拉道路：欧拉定理+并查集（判断连通性） 4.考虑如何统计每个顶点的度，开始用的是暴力解法，直接用数组记录顶点，并且通过顺序查找获得顶点编号，TLE，然后考虑用map（红 ...