Poj 3352 Road Constructionエッジ二重連通成分tarjanアルゴリズム

http://poj.org/problem?id=3352
标题:n都市mの道があり、最初はどの2都市も互いに達することができた.今は道路を修理する必要があります.道路を修理するときは通行できません.そして、どの2つの都市も互いに達成できるように、臨時の橋を建設する必要があります.最低で建設する必要がある橋の数量を求めます.
題解:これは無方向図で、1本の辺を取り除くと連通しません.では、この辺が橋です.今は臨時の橋を建てて、建て終わったら原図と一緒に、この有向図は辺が二重に連通している(辺連通度が1より大きい).今、いくつかのエッジを加えて、この無方向図がエッジに二重に連通するようにします.
まずtarjanはエッジ二重連通成分を求め,エッジ二重連通成分を縮点すると木が形成される.
次に,1本の木について,エッジをどのように付けてエッジを二重に連通させるかについて,エッジ数=(葉ノード数+1)/2という結論が得られた.すなわち、加辺後の無度数が1の点である.
コード:

#include
#include