[問題] graph dfs問題

[Ninja5566 (苦味)]

因為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
→ firejox:開相鄰矩陣~~~
→ firejox:讀入i,j s[i][j]=s[j][i]=1
→ Ninja5566:因為太大所以沒辦法開  題目強迫不能用n*n陣列作
→ firejox:用vector做相鄰串列
→ firejox:比較直觀
→ Ninja5566:這不是直不直觀= = 題目最多給到500000*500000
→ Ninja5566:所以太大做不出來
→ firejox:50000*50000? 是點還是邊？
→ Ninja5566:記錯 人最多30000
→ Ninja5566:但edge<500000
→ bleed1979:可以說是那一題嗎？謝謝。
→ Ninja5566:囧其實我已經做出來了  只是想知道比較好的寫法
→ Ninja5566:acm 10608 friends
→ bleed1979:Disjoint Sets，請估狗演算法筆記。
→ firejox:哦哦 並查集
→ firejox:補AC code http://codepad.org/HL4A9Zc5
→ firejox:補 vector http://codepad.org/8ElmkFpk