[問題] graph dfs問題
因為input size 很大 所以不得不把pair放成這樣
以下是sort之後結果
vertex: 1 2 3 4 5 6 7 8 9 10
index: 0 7 1 5 3 -1 8 11 10 -1
index: 0 9 7 1 2 4 5 3 6 8 11 10
head: 1 1 2 3 3 3 4 5 5 7 8 9
tail: 2 2 1 1 4 5 6 4 2 10 9 10
input長這樣:
1 2
3 1
3 4
5 4
3 5
4 6
5 2
2 1
7 10
1 2
9 10
8 9
這是我sort完的結果 我現在想要跑DFS
可是題目其實是一個雙向圖 他只有給單向
所以像vertex10 雖然有edge 可是因為方向關係會比較難找
那要跑的話大家會推荐怎麼做呢?
我有想到以下幾種方法 不知道好不好
1.把陣列大小變兩倍 各放一條反方向edge再sort
2.再建一個index的陣列 但是用反方向sort陣列
3.如果直接找找不到 直接用迴圈找
還是有其他比較好的方法?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.121.147.25
→
04/15 20:38, , 1F
04/15 20:38, 1F
→
04/15 20:47, , 2F
04/15 20:47, 2F
→
04/15 21:29, , 3F
04/15 21:29, 3F
→
04/15 23:17, , 4F
04/15 23:17, 4F
→
04/15 23:19, , 5F
04/15 23:19, 5F
→
04/15 23:50, , 6F
04/15 23:50, 6F
→
04/15 23:51, , 7F
04/15 23:51, 7F
→
04/16 00:01, , 8F
04/16 00:01, 8F
→
04/16 00:05, , 9F
04/16 00:05, 9F
→
04/16 00:05, , 10F
04/16 00:05, 10F
→
04/16 00:07, , 11F
04/16 00:07, 11F
→
04/16 00:10, , 12F
04/16 00:10, 12F
→
04/16 00:11, , 13F
04/16 00:11, 13F
→
04/16 00:29, , 14F
04/16 00:29, 14F
→
04/16 01:08, , 15F
04/16 01:08, 15F
→
04/17 01:19, , 16F
04/17 01:19, 16F
→
04/17 01:34, , 17F
04/17 01:34, 17F
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
