網頁

2014年5月22日 星期四

POJ 2117 Electricity

題意:
    這題是將graph中移除一個點,graph會變成D個獨立部分,求D的最大値。
    第一行輸入P和C表示有P個點(0~P-1)和C條邊,每條邊都是雙向的。

想法:
    分成兩個
  1. 如果C==0表示P個點沒有任何的邊,直接輸出P-1
  2. 本來的圖就分成N部分(N可能==1表示所有點都是連通的,但N也可能>1),移除某個點i能將該部分再分成cut[i]部分,那麼其中一個候選答案為N+cut[i]-1,找到最大的候選答案。套Cut Vertex模板求cut[i]。
    第二點舉個例子:
5 3
0 1
1 2
3 4
表示0,1,2和3,4不連通,所以N==2,N是固定的,然後例如移除點1,cut[1]==2(因為(0,1,2)這部分移除點1會將0,2分開變成2個部分),因此候選答案就是2+2-1=3,也是這個測資的解答。