有n顆雷達中間有m條電纜連接,任意兩顆雷達間都存在唯一一條最短路徑,每個雷達都有自己的通訊頻率。為了避免雷達間互相干擾,任兩顆相鄰的雷達需使用不同的通訊頻率。請問最少需要使用到幾種不同的頻率來進行通訊?
第一行有兩個整數$N$,$M$
接下來有$M$行$x, y$,代表$x$號雷達與$y$號雷達間有一條電纜。
$1 \leq N \leq 10^5$
$ 1 \leq M \leq 10^6$
$1 \leq x,y \leq N$
輸出一個整數,代表最少須用到的頻率數量。
5 4 1 2 1 3 2 4 2 5
2
在範例中,可以將1,4,5使用同一種頻率,2,3使用同一種頻率,最少需要2種
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
155 |
jeremydinger...
(164253)
|
c094 | 164 | 2023-06-28 20:58 |