Problem
給予一張有向森林圖,要求任兩點若有一條路徑,則兩點不可著相同顏色,請問最少著色數為何?
Sample Input
|
|
Sample Output
|
|
Solution
明顯地,最長路徑長度若為 $L$,至少需要 $L$ 個顏色,因此針對每一個樹根進行最長路徑搜索即可,又由於題目給定森林,把每一個樹根抓出來取最大值即可。複雜度 $\mathcal{O}(N)$
|
|
給予一張有向森林圖,要求任兩點若有一條路徑,則兩點不可著相同顏色,請問最少著色數為何?
|
|
|
|
明顯地,最長路徑長度若為 $L$,至少需要 $L$ 個顏色,因此針對每一個樹根進行最長路徑搜索即可,又由於題目給定森林,把每一個樹根抓出來取最大值即可。複雜度 $\mathcal{O}(N)$
|
|