儲存一張圖的方式有許多種,比較常見的像是:adjacency matrix、adjacency lists。
adjacency matrix是用一個二維的陣列去紀錄一個node有沒有連到另一個node。但是有些時候一個node 連到的 node數量可能會過多,導致adjacency matrix的二維陣列無法存起來。例如,當node數大於100000時,adjacency matrix會達到10^10,記憶體會過大。這時候,我們就會改用adjacency lists去紀錄。
adjacency lists的紀錄方法是:對於每個node開一個link list,然後把有連線的node串在這條link list上。
有多筆測資,測資第一行有兩個數字n,m
n (1
m (1
接下來的m行,每行有一個指令:
1. Connect a b : 將a可以連到 b,保證不會重複連線,且自己不會和自己連線
2. Ask a b : 詢問a是否可以連到b,可以的話輸出”Yes”,反之輸出”No”
3. Cut a b : 將a到b的連線剪斷,如果a到b本來沒有連線請輸出”Error”
連線都是單向的,a連到b不表示b可以連到a
對於Ask, Cut指令請按照規則輸出