對於 u, v ∈ V 必然會存在一條最短路徑,而 I (u, v) 定義為在 u - v 最短路徑上的點所產生的集合,而 S ⊆ V,
如果 I(D) = V,則這節點集合 D 被稱作為 G 的其中一個 geodetic set, The geodetic set problem 就是要檢驗 D 是否為 geodetic set。
以上圖為例,I(2, 5) = {2, 3, 4, 5},即所有可能在最短路徑上的所有點,然而
I(2, 5) 並不是一個 geodetic set,因為並不等於 {1, 2, 3, 4, 5}。
假如 D = {1, 2, 5},則 I(D) = V,同時 {1, 3, 4} {1, 4, 5} 也都是 geodetic set,但
{3, 4, 5} 卻不是,因為節點 1 並不在 I(D) 中。
Input
輸入有多組測資,每組第一行有一個整數 n (2 <= n <= 40) 表示圖有多少節點。
接下來會有 n 行,在第 i 行(1 <= i <= n)上會有數個整數,表示與節點編號 i 相連的點。
接著會有一行一個整數 q,表示接下有多少組詢問。
每組詢問一行,行上的每個整數 D 集合內的節點編號。
Output
對於每組詢問的 D,判斷 D 是否為 geodetic set。
Sample Input
5
2 3
1 3 4
1 2 5
2 5
3 4
6
1 2 3 4 5
1 2 5
2 4
1 3 4
1 4 5
3 4 5
Sample Output
yes
yes
no
yes
yes
no
沒有留言:
張貼留言