Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

我的一点体会,大家仅供参考,主要是欧拉路径是否存在的判定及欧拉路径起点的寻找

Posted by Maxwell_pp at 2016-11-24 10:01:36 on Problem 2337
若是从欧拉路径的角度来做,我犯了两个错,对大家来说可能比较低级,但说不定也有点参考作用:
1.欧拉路径是否存在的判断,主要是通过节点的度来做。一个节点的出度与入度有四种情况,分为是:
出度等于入度,这是欧拉路径的中间节点
出度等于入度-1, 如果欧拉路径存在,这样的节点应该最多只有一个
入度等于出度-1,如果欧拉路径存在,这样的节点应该最多一个
其它情况,这样的节点一旦存在,必须没有欧拉路径。
考虑这样的数据:
3
w
ww
www
此时所有节点的出度都等于入度。因此,情况2和情况3的点要么都没有,要么都只有一个。否则必然没有欧拉路径。

2.关于起点的判断。简单无向图中将情况出度比入度多1的点做起点,但考虑上面那个例子,不存在这样的点,因此要注意,在上面这种情况下,将起点选成排序后的第一个字符串。

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator