藍橋杯 曆屆試題 危險系數

<code>  </code><code>曆屆試題 危險系數 </code>

<code>時間限制：1.0s   記憶體限制：256.0MB</code>

<code>      </code> 

<code>問題描述</code>

<code>抗日戰争時期，冀中平原的道地戰曾發揮重要作用。</code>

<code>道地的多個站點間有通道連接配接，形成了龐大的網絡。但也有隐患，當敵人發現了某個站點後，其它站點間可能是以會失去聯系。</code>

<code>我們來定義一個危險系數DF(x,y)：</code>

<code>對于兩個站點x和y (x != y), 如果能找到一個站點z，當z被敵人破壞後，x和y不連通，那麼我們稱z為關于x,y的關鍵點。相應的，對于任意一對站點x和y，危險系數DF(x,y)就表示為這兩點之間的關鍵點個數。</code>

<code>本題的任務是：已知網絡結構，求兩站點之間的危險系數。</code>

<code>輸入格式</code>

<code>輸入資料第一行包含2個整數n(2 &lt;= n &lt;= 1000), m(0 &lt;= m &lt;= 2000),分别代表站點數，通道數；</code>

<code>接下來m行，每行兩個整數 u,v (1 &lt;= u, v &lt;= n; u != v)代表一條通道；</code>

<code>最後1行，兩個數u,v，代表詢問兩點之間的危險系數DF(u, v)。</code>

<code>輸出格式</code>

<code>一個整數，如果詢問的兩點不連通則輸出-1.</code>

<code>樣例輸入</code>

<code>7 6</code>

<code>1 3</code>

<code>2 3</code>

<code>3 4</code>

<code>3 5</code>

<code>4 5</code>

<code>5 6</code>

<code>1 6</code>

<code>樣例輸出</code>

<code>2</code>

<a></a>

本文轉自 小眼兒 部落格園部落格，原文連結：http://www.cnblogs.com/hujunzheng/p/4356993.html，如需轉載請自行聯系原作者