[ACM ] 247 calling circles (done)
題號：
247 http://0rz.tw/KkkbG
code http://nopaste.csie.org/dd222
是找 trsitive closure (if A->B and B->C ==> A->C) 的相關問題
想找出所有的trsitive closure
遇到的問題：
WA (不知道是演算法本身有問題還是輸出格式...orz)
希望大家幫我看看~~
補充說明：
這題因為題目中的vertex不多 所以我用adj_matrix來儲存相鄰關係的訊息
對每個vertex都去檢查可走到的點
最後如果 A->B 且 B->A 那麼就判定 A B 屬於同一個群體之中
謝謝大家~
algo :
1. 我先對每個點都先看它可以走到哪些點
如果A[x][j] == 1 : 表示 x, j 兩點可通
再check 如果A[j][i] == 1 : 表示j, i 兩點可通 那麼x, i 也會互通
最後就建出新的adj_list
2. set A[i][i] == 0 i = 1 ~ n (用來check是否第一個點 只是方便輸出格式)
3. 如果 A[i][j] == 1 而且 A[j][i] == 1 表示i, j互通 在同一個群體上
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.43.164.63
※ 編輯: christianSK 來自: 114.43.164.63 (05/22 11:20)
※ 編輯: christianSK 來自: 114.43.164.63 (05/22 11:21)
※ 編輯: christianSK 來自: 114.43.164.63 (05/22 11:22)
推
05/22 13:08, , 1F
05/22 13:08, 1F
→
05/22 13:08, , 2F
05/22 13:08, 2F
→
05/22 14:24, , 3F
05/22 14:24, 3F
※ 編輯: christianSK 來自: 114.43.164.63 (05/22 14:32)
推
05/22 18:05, , 4F
05/22 18:05, 4F
→
05/22 18:06, , 5F
05/22 18:06, 5F
→
05/22 20:57, , 6F
05/22 20:57, 6F
→
05/22 20:57, , 7F
05/22 20:57, 7F
→
05/22 20:58, , 8F
05/22 20:58, 8F
→
05/22 21:01, , 9F
05/22 21:01, 9F
→
05/23 02:35, , 10F
05/23 02:35, 10F
→
05/23 18:31, , 11F
05/23 18:31, 11F
推
05/24 04:46, , 12F
05/24 04:46, 12F
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
