摘要: 研究了Lynncui牛的代码,才知道解题思路:
先Tarjan强连通缩点,(假设共n2个)得到的id[i]编号为0的分支,其出度为0(有可能是Popular Cows)。
再判断其他强连通分支是否有出度
1)如果其中有一个分支没有出度,则0分支不可能是Popular Cows(considered popular by every other cow)
2)如果其他所有强连通分支都有出度,
阅读全文
posted @
2009-04-23 18:17 longshen 阅读(590) |
评论 (0) |
编辑 收藏
摘要: 思路模糊时看了DieIng大牛的思路,写了出来...
思路:Tarjan算法计算强连通分支,然后缩点,再求其拓扑序。
(假设求得的拓扑序存储在topo[MAX]中) topo[i] 与 topo[i+1] 存在边连通(i到i+1 或i+1到i),则定有i到i+1的边。
而如果每个topo[i] 与 topo[i+1] 都存在边连通(即有i到i+1的边)时,topo[i] 到任意topo[j]便都要边连通。
阅读全文
posted @
2009-04-23 09:08 longshen 阅读(528) |
评论 (0) |
编辑 收藏