摘要: 研究了Lynncui牛的代碼,才知道解題思路:
先Tarjan強(qiáng)連通縮點(diǎn),(假設(shè)共n2個)得到的id[i]編號為0的分支,其出度為0(有可能是Popular Cows)。
再判斷其他強(qiáng)連通分支是否有出度
1)如果其中有一個分支沒有出度,則0分支不可能是Popular Cows(considered popular by every other cow)
2)如果其他所有強(qiáng)連通分支都有出度,
閱讀全文
posted @
2009-04-23 18:17 longshen 閱讀(612) |
評論 (0) |
編輯 收藏
摘要: 思路模糊時看了DieIng大牛的思路,寫了出來...
思路:Tarjan算法計(jì)算強(qiáng)連通分支,然后縮點(diǎn),再求其拓?fù)湫颉?
(假設(shè)求得的拓?fù)湫虼鎯υ趖opo[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 閱讀(551) |
評論 (0) |
編輯 收藏