Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
我的一点体会,大家仅供参考,主要是欧拉路径是否存在的判定及欧拉路径起点的寻找若是从欧拉路径的角度来做,我犯了两个错,对大家来说可能比较低级,但说不定也有点参考作用: 1.欧拉路径是否存在的判断,主要是通过节点的度来做。一个节点的出度与入度有四种情况,分为是: 出度等于入度,这是欧拉路径的中间节点 出度等于入度-1, 如果欧拉路径存在,这样的节点应该最多只有一个 入度等于出度-1,如果欧拉路径存在,这样的节点应该最多一个 其它情况,这样的节点一旦存在,必须没有欧拉路径。 考虑这样的数据: 3 w ww www 此时所有节点的出度都等于入度。因此,情况2和情况3的点要么都没有,要么都只有一个。否则必然没有欧拉路径。 2.关于起点的判断。简单无向图中将情况出度比入度多1的点做起点,但考虑上面那个例子,不存在这样的点,因此要注意,在上面这种情况下,将起点选成排序后的第一个字符串。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator