※ 引述《Leon (Achilles)》之铭言：
: 标题: Re: [问题] 在O(|V|)的时间内找到non-cut点
: 时间: Wed Jul 31 01:49:38 2013
:
: ※ 发信站: 批踢踢实业坊(ptt.cc)
: ◆ From: 76.170.77.110
: 推 seanwu:non-cut point可以不是leaf，例如完全图上任何一点都是 07/31 02:03
: → Leon:that's correct, however, my algo just want to find one 07/31 02:09
: 推 seanwu:噢! 我误会了你的意思了，你是指spanning tree吗? 07/31 02:10
: → Leon:其实, non-cut point is a leaf in one spanning tree 07/31 02:10
: → Leon:看来你了解了, good 07/31 02:11
: → seanwu:哈... 因为你第三行突然冒出"a tree"，一时没转过来XD 07/31 02:15
: → seanwu:不过我觉得step 2.应该不是O(K)? 最差可以到 O(K^2) 吧? 07/31 02:16
: → seanwu:如果是需要看过这些edge，把他们挑出来的话 07/31 02:17
: → Leon:这就是巧妙的地方, 你去试一个图做看看就知道 07/31 03:23
: 推 FRAXIS:我也觉得在第二步的时候会需要O(k^2)的时间 有什么技巧嘛？ 07/31 04:23
技巧就是说破了不值一毛钱的小东西.
举个简单的例子, 4 Node graph, as a ring.
The neighboring matrix is
0 1 0 1 ;
1 0 1 0 ;
0 1 0 1 ;
1 0 1 0 ;
So.. if you start from the first node, you will find neighbors are
V_2 and V_4. In step 1, it takes 2 operations to look at the E_{1,j}.
Then, you modify the neighboring matrix, remove the edges
E_{1,2} -> E_{2,1} and E_{1,4} -> E_{4,1}.
Because we don't need loop in spanning tree.
In step 2, you start to look at node 2,
now it only takes you 1 operation to get V_3
because edge E_{2,1} has been removed in previous step.
Follow this concept, I guess you only need O(|V|).