g*****e
发帖数: 282 | 1 今天下午请假连续电面。图论还没复习到，挂定了。搞了半天，最后给了个work但很纠
结的方法。前面是跟leetcode上的类似题，顺利搞定。
总觉得电话面试考这种题很难讨论，虽然对方人很nice也很耐心。。。
Cactus graph
http://en.wikipedia.org/wiki/Cactus_graph |
f*****e
发帖数: 2992 | 2 edges一个一个的删直到删任何一个edge就disjoint？cycles=原有edges-剩下的edges=
m-(n-1)
=m-n+1？
【在 g*****e 的大作中提到】
: 今天下午请假连续电面。图论还没复习到，挂定了。搞了半天，最后给了个work但很纠
: 结的方法。前面是跟leetcode上的类似题，顺利搞定。
: 总觉得电话面试考这种题很难讨论，虽然对方人很nice也很耐心。。。
: Cactus graph
: http://en.wikipedia.org/wiki/Cactus_graph
|
g*****e
发帖数: 282 | 3 good。我写了一些test cases都是对的。
这题还要写code实现的。请问怎么写code判断是否idsjoint效率最高，如果graph用
adjmatrix描述的？
graph还没复习，现在就翻书去。。。
edges=
【在 f*****e 的大作中提到】
: edges一个一个的删直到删任何一个edge就disjoint？cycles=原有edges-剩下的edges=
: m-(n-1)
: =m-n+1？
|
f*****e
发帖数: 2992 | 4 如果告诉你G是cactus graph，并且有m条边，n个点，cycles数目就直接可以算出来了m
-n+1。如果没有告诉你m和n，你遍历G，求出m和n，然后再算m-n+1就行了。
【在 g*****e 的大作中提到】
: good。我写了一些test cases都是对的。
: 这题还要写code实现的。请问怎么写code判断是否idsjoint效率最高，如果graph用
: adjmatrix描述的？
: graph还没复习，现在就翻书去。。。
:
: edges=
|
g*****e
发帖数: 282 | 5 问题还没完，接下来是怎么把各个cycles找出来。我没来得及coding
咱们继续讨论吧 =)
了m
【在 f*****e 的大作中提到】
: 如果告诉你G是cactus graph，并且有m条边，n个点，cycles数目就直接可以算出来了m
: -n+1。如果没有告诉你m和n，你遍历G，求出m和n，然后再算m-n+1就行了。
|
z********i
发帖数: 568 | 6 删degree=2的点吧？最后剩下的都是有两条self-loop的isolated vertices: each
vertex corresponds two cycles.
edges=
【在 f*****e 的大作中提到】
: edges一个一个的删直到删任何一个edge就disjoint？cycles=原有edges-剩下的edges=
: m-(n-1)
: =m-n+1？
|
f*****e
发帖数: 2992 | 7 很简单的，先把spanning tree给找出来，记为G',
for evey e=(u,v) in E(G)-E(G')
the path from u to v in G' together with e form a cycle in G
【在 g*****e 的大作中提到】
: 问题还没完，接下来是怎么把各个cycles找出来。我没来得及coding
: 咱们继续讨论吧 =)
:
: 了m
|
g*****e
发帖数: 282 | 8 哇塞。牛人啊。图论底子扎实。
我发现自己超出leetcode题目知识范围的题就不行了。如果考个network flow也是必挂
。抓紧时间看书。。。
【在 f*****e 的大作中提到】
: 很简单的，先把spanning tree给找出来，记为G',
: for evey e=(u,v) in E(G)-E(G')
: the path from u to v in G' together with e form a cycle in G
|
