7232 - PI - Adjacency List   

Description

儲存一張圖的方式有許多種,比較常見的像是: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上。

Input

有多筆測資,測資第一行有兩個數字n,m

n (1表示node數,其中node編號從0n-1

m (1表示指令的數量。

接下來的m行,每行有一個指令:

1.      Connect a b : a可以連到 b,保證不會重複連線,且自己不會和自己連線

2.      Ask a b : 詢問a是否可以連到b,可以的話輸出”Yes”,反之輸出”No”

3.      Cut a b : ab的連線剪斷,如果ab本來沒有連線請輸出”Error”

連線都是單向的,a連到b不表示b可以連到a

Output

對於Ask, Cut指令請按照規則輸出

Sample Input  Download

Sample Output  Download

Tags




Discuss