APCS202306第4題 開啟寶盒

輸出說明

輸出一個正整數，代表可以開啟的寶盒數量。

範例輸入 #1

5 5 1

2 0 1

0

2

4

3

1

1

2

4

3

3

範例輸出 #1

3

範例輸入 #2

10 8 2

3 6 5 2

5 6

2 7

2 0

4 5

5 1

3 0

4 2

2 4

5 3

5 6

5 0

0 6

1 7

3 2

2 1

7 3

4 7

4 5

4 1

7 5

範例輸出 #2

5

鑰匙可以重複使用，只要有該種類的鑰匙就可以開所有需要該鑰匙的寶盒。

使用一維的deque記錄每個key可以開啟的寶盒，命名為key。使用一維的deque記錄每個box可以獲得的鑰匙，命名為box。

Step1)將開始的t種鑰匙加入陣列has，每次拿一把鑰匙開啟能開啟的寶盒，且visit確認每種鑰匙只考慮一次，該開始寶盒的in-degree為k，每找到一個鑰匙，in-degree就遞減1。

Step2)若該寶盒的k個鑰匙都找到，in-degree會是0，則將能獲得的鑰匙，去除重複加到陣列has，能開啟的寶盒增加1。

Step3)重複以上動作直到陣列has為空的。

此演算法類似於拓樸排序(topological sorting)。