1433 問題 I: 藍橋杯2013年第四屆真題-危險系數(shù)
時間限制: 1s
內(nèi)存限制: 128MB 提交: 6898 解決: 2290
題目描述
問題描述
抗日戰(zhàn)爭時期，冀中平原的地道戰(zhàn)曾發(fā)揮重要作用。
地道的多個站點間有通道連接，形成了龐大的網(wǎng)絡。但也有隱患，當敵人發(fā)現(xiàn)了某個站點后，其它站點間可能因此會失去聯(lián)系。
我們來定義一個危險系數(shù)DF(x,y)：
對于兩個站點x和y (x != y), 如果能找到一個站點z，當z被敵人破壞后，x和y不連通，那么我們稱z為關(guān)于x,y的關(guān)鍵點。相應的，對于任意一對站點x和y，危險系數(shù)DF(x,y)就表示為這兩點之間的關(guān)鍵點個數(shù)。
本題的任務是：已知網(wǎng)絡結(jié)構(gòu)，求兩站點之間的危險系數(shù)。
輸入
輸入數(shù)據(jù)第一行包含2個整數(shù)n(2 < = n < = 1000), m(0 < = m < = 2000),分別代表站點數(shù)，通道數(shù)；
接下來m行，每行兩個整數(shù) u,v (1 < = u, v < = n; u != v)代表一條通道；
最后1行，兩個數(shù)u,v，代表詢問兩點之間的危險系數(shù)DF(u, v)。
輸出
一個整數(shù)，如果詢問的兩點不連通則輸出-1.
樣例輸入
7 6
1 3
2 3
3 4
3 5
4 5
5 6
1 6
提示
零基礎同學可以先學習
視頻課程，包含C/C++、Python、百練、藍橋杯輔導、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習題，還有老師答疑，
點擊這里了解課程詳情