題解/算法 {1183. 电力}

題解/算法 {1183. 电力}

題解/算法 {1183. 电力}
@LINK: /;

這個題 涉及到無向圖的(連通塊) 這個概念, 即刪除一個點後 新圖的連通塊的個數; 比如a, b-c-d 此時有2個連通塊, 刪除a後 只有1個連通塊, 刪除b/d後 有2個連通塊, 刪除c後 有3個連通塊;
注意 比如答案是刪除x點, 這個點 不一定是(割點), 因為原圖可能就不存在割點, 當然 如果有割點 答案肯定是割點; 因此我們的做法是: 枚舉(刪除每個點)的情況, 而不是只枚舉(刪除割點)!

要解決這個題, 你必須非常的清楚Tarjan_CutPoint這個算法, 因為這個算法本身對於每個點 都有一個cc_count 就是表示(刪除這個點之後 他所在的連通子圖 會分裂成cc_count個連通塊);
. 即 對於上面的樣例 cc_count[a,b,c,d] = [0,1,2,1] (比如對於a 他所在的連通子圖為a 你刪除這個點後 這個圖就沒有連通塊了);

因此, 令Ma = max( cc_count[...]), 令All = 連通子圖的個數, 則答案為All - 1 + Ma;

筆記

Let C C 1 , . . . , C C k CC1, ..., CCk CC1,...,CCk be all the CC of the graph G G G, the CC-count of this graph is k k k; we want to know the maximal CC-count of G 1 G1 G1 obtained by deleted one point (and its all adjacent-edges) from G G G;
Note that we must remove one point, suppose that this point a a a belongs to C C i CCi CCi; then the answer equals ( k − 1 ) + x (k-1) + x (k−1)+x where x x x is the CC-count of C C i CCi CCi after removed a a a; our goal is to calculate x x x;

If C C i CCi CCi has no Cut-Point, then you can choose an arbitrary point as a a a;
Otherwise, by the property of Cut-Point, it must divided into x ≥ 2 x geq 2 x≥2 CC after removed a Cut-Point, so, we iterate all Cut-Point in this case;

But, do not just iterate just for all Cut-Points, cuz C C CC CC may not contains any Cut-Points in such case x = 0 x = 0 x=0 if CC has just one point otherwise x = 1 x = 1 x=1;

Actually, x x x (the new CC-count after remove any point from a C C CC CC) is already calculated in the Canonical-Tarjan-Algorithm for P B C C PBCC PBCC, we just directly use it;

ma = 0;
int count = 0;
for( int i = 0; i < graph->Get_pointsCount(); ++i){if( -1 == dfs_id[ i]){++ count;dfs_startPoint = i;dfs( i);}
}
Ans = count - 1 + ma;
//--
void dfs( _cur){int cc_count = 0;... The canonical-algorithm of Tarjan for PBCC;//>< `cc_count` means the number of Connected-Component when `_cur` was removed from the current Connected-Component (whatever `cur` is Cut-Point or not);Ans = max( cc_count, Ans); //< donot write that `if( cur is Cut-Point){ ...}`
}