Detail of message

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

大水牛来

Posted by sunmoonstar_love at 2005-09-01 16:47:31
In Reply To:求有向无环图的传递闭包有 O(e)的算法么？有O(n^2)的？ Posted by:sunmoonstar_love at 2005-09-01 16:27:41

Followed by:

UP (0) sunmoonstar_love 2005-09-01 20:15:35
UP (0) sunmoonstar_love 2005-09-01 20:41:50
- 你说的传递闭包是不是就是用floyd来判断图的连通性？ (0) Spacesheep 2005-09-01 22:44:31
  - 什么是传递闭包？ (0) frkstyc 2005-09-01 22:53:06
    - 就是判断每对点是否可达，不过 floyd 显然太慢了 (0) sunmoonstar_love 2005-09-02 02:11:54
      - 有向有环图也是O(e)吧 (0) zhougelin 2005-09-02 09:39:34
        上贴作废 (0) zhougelin 2005-09-02 09:40:56
      - 枚举每条边+disjoint set。。。我知道的最好的方法就是这样了。。。 (0) Spacesheep 2005-09-02 10:41:23
        那个是无向图吧？ (0) sunmoonstar_love 2005-09-02 10:52:58
        sorry,看错了 (0) Spacesheep 2005-09-02 13:17:54

Post your reply here:

Home Page Go Back To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator