題目連結

https://zerojudge.tw/ShowProblem?problemid=b343

https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2513

參考文章

建議點開看一下～

感謝大大提供的測試資料，多這兩筆測試資料在解決時會更好debug！

[email protected]（蛋黃酥）#38314: 提供更好的測資

這邊幫各位整理好三筆測資

範例輸入 1

1
5 8 2
1 2
1 3
2 3
3 2
3 4
4 1
4 2
4 5
1
4

範例輸入 2

1
6 6 1
2 1
2 3
2 4
2 5
2 6
6 2
6

範例輸入 3

1
3 2 1
1 2
2 3
2

範例輸出 1

5

範例輸出 2

6

範例輸出 3

2

本題要點

會使用到的骨牌編號為 1 到 𝑛（已知範圍，所以我選擇用下面的方法解決）

首先我們宣告一個二維陣列名為 dominos[n+1]，裡面每個位置都是空陣列 []

當推倒骨牌 i 時，dominos[ i ] 就會紀錄將被 i 骨牌推倒的骨牌編號

下面有個例子

n = 5
dominos = [ [], [], [], [], [], [] ]
		         ^   ^   ^   ^   ^   ^
		idx =    0.  1.  2.  3.  4.  5.

當我們知道推倒骨牌 4 會造成骨牌 1, 2, 5 倒下時
dominos 陣列會變成下方的樣子

dominos = [ [], [], [], [], [1, 2, 5], [] ]
		         ^   ^   ^   ^       ^      ^
		idx =    0.  1.  2.  3.      4.     5.

我拿範例輸入 1 來當示範，資料輸入後的 dominos 陣列為

dominos = [ [], [2, 3], [3], [2, 4], [1, 2, 5], [] ]