原題來自:USACO 2006 Jan. Gold
為了從 F個草場中的一個走到另一個,貝茜和她的同伴們不得不路過一些她們討厭的可怕的樹。奶牛們已經(jīng)厭倦了被迫走某一條路,所以她們想建一些新路,使每一對草場之間都會至少有兩條相互分離的路徑,這樣她們就有多一些選擇。
每對草場之間已經(jīng)有至少一條路徑,給出所有 R 條雙向路的描述,每條路連接了兩個不同的草場,請計算最少的新建道路的數(shù)量。
路徑由若干道路首尾相連而成,兩條路徑相互分離,是指兩條路徑?jīng)]有一條重合的道路,但是兩條分離的路徑上可以有一些相同的草場。
對于同一對草場之間,可能已經(jīng)有兩條不同的道路,你也可以在它們之間再建一條道路,作為另一條不同的道路。
7 7 1 2 2 3 3 4 2 5 4 5 5 6 5 7
2
樣例解釋:
圖中虛線表示已有的道路,點線表示新建的兩條道路?,F(xiàn)在可以檢驗一些路徑,比如:
草場 1 和草場 2:1→2 和 1→6→5→2
草場 1 和草場 4:1→2→3→4 和 1→6→5→4
草場 3 和草場 7:3→4→7 和 3→2→5→7
事實上,每一對草場之間都連接了兩條分離的路徑。
數(shù)據(jù)范圍與提示:
1≤F≤5000,F?1≤R≤10000。