DissCode | Problem Details

[Desgard]

http://disscode.com/problem/DSC1003

[Desgard]

遇到坑的同学从几个角度来考虑这个问题：

1. 对于有向图来说 (1) -> (2) 、(2) -> (1) 这个是环，但对于无向图来说 (1) - (2) 不是环。有向图而言，环等于回路；
2. 如果使用前向星来描述图，注意无向图边去重。

[shevakuilin]

《判断图中是否存在环》这题，在有向图中，1->2, 2->3, 3->1 算存在环，那如果是 1-> 2, 1->3, 3->2, 这种也算环吗？我感觉应该不算，因为无法形成回路

[Desgard]

@shevakuilin 《判断图中是否存在环》这题，在有向图中，1->2, 2->3, 3->1 算存在环，那如果是 1-> 2, 1->3, 3->2, 这种也算环吗？我感觉应该不算，因为无法形成回路

不算的。有向图要看是否有回路。其实题目里少了描述，有向图 1 -> 1 这种应该也算环（自环），但是 test case 应该是没有这种数据的。

[shevakuilin]

@Desgard

@shevakuilin 《判断图中是否存在环》这题，在有向图中，1->2, 2->3, 3->1 算存在环，那如果是 1-> 2, 1->3, 3->2, 这种也算环吗？我感觉应该不算，因为无法形成回路

不算的。有向图要看是否有回路。其实题目里少了描述，有向图 1 -> 1 这种应该也算环（自环），但是 test case 应该是没有这种数据的。

无向图里的 (1) - (1) 也应该算自环？

[Desgard]

@shevakuilin

@Desgard

@shevakuilin 《判断图中是否存在环》这题，在有向图中，1->2, 2->3, 3->1 算存在环，那如果是 1-> 2, 1->3, 3->2, 这种也算环吗？我感觉应该不算，因为无法形成回路

不算的。有向图要看是否有回路。其实题目里少了描述，有向图 1 -> 1 这种应该也算环（自环），但是 test case 应该是没有这种数据的。

无向图里的 (1) - (1) 也应该算自环？

原则上应该算。但是这道题目大前提是不考虑自环、不考虑重边。具体要看题里的定义，感觉题目条件不太严谨才会造成这些误解。