題：風險度量 X星系的的防衛體系包含 n 個空間站。這 n 個空間站間有 m 條通信鏈路，構成通信網。 兩個空間站間可能直接通信，也可能通過其它空間站中轉。 對于兩個站點x和y (x != y), 如果能找到一個站點z，使得： 當z被破壞后，x和y無法通信，則稱z為關于x,y的關鍵站點。 顯然，對于給定的兩個站點，關于它們的關鍵點的個數越多，通信風險越大。 你的任務是：已知網絡結構，求兩站點之間的通信風險度，即：它們之間的關鍵點的個數。 輸入數據第一行包含2個整數n(2 <= n <= 1000), m(0 <= m <= 2000),分別代表站點數，鏈路數。 空間站的編號從1到n。通信鏈路用其兩端的站點編號表示。 接下來m行，每行兩個整數 u,v (1 <= u, v <= n; u != v)代表一條鏈路。 最后1行，兩個數u,v，代表被詢問通信風險度的兩個站點。 輸出：一個整數，如果詢問的兩點不連通則輸出-1. 例如： 用戶輸入： 7 6 1 3 2 3 3 4 3 5 4 5 5 6 1 6 應該輸出： 2 */ #include<iostream> using namespace std; int pre[1002]={0};//存放每個頂點的前節點 //尋找x的前節點 int find(int x) { return pre[x] == x ? x : pre[x] = find(pre[x]); } //join將有關的節點進行連接 void join(int x,int y) {//將后一個節點作為前一個節點的根pre[find(x)] = find(y); } int main() {int n;int link;int u[1002]={0};int v[1002]={0};int a,b;cin>>n>>link; for(int i = 1; i <= n; i++) //初始化站點編號 {pre[i] = i;}for(int i = 0; i < link; i++){cin>>u[i]>>v[i];join(u[i],v[i]);}cin>>a>>b;if(find(a)!=find(b))//說明不連通{cout<<"-1"<<endl; return 0; } else//說明是連通的 {int ans = 0;//記錄關鍵節點個數 //判斷如果與某個點相關聯的邊都不存在了，是否連通，不聯通說明該點為關鍵點//對每個點判斷，暴力for(int i = 1; i <= n; i++){if(i==a || i==b) continue;//將pre數組重置 for(int k = 1; k <= n; k++){pre[k] = k;} for(int j = 0; j < link; j++){if(i==u[j] || i==v[j]) continue;else{join(u[j],v[j]);}} if(find(a)!=find(b))//不聯通了 {ans++;}} cout<<ans<<endl;return 0;} }

解法二：

#include<iostream> using namespace std; int link[1002][1002];//連接表 int count[1002]={0};//每個數字走過的次數 bool visit[1002];//標記是否走過 int roads=0;//統計路的個數 int b; int n,m; void dfs(int a)//a是變參 {if(a==b)//連通到最后一個點了 {roads++;//將路的數目加1 for(int i = 1; i <= n; i++)//將所有走過的點的個數加1 {if(visit[i]==true){count[i]++;}} }else//否則繼續遍歷 {for(int i = 1; i <= n; i++){if(visit[i]==false && link[a][i]==1){visit[i] = true;dfs(i);visit[i] = false;}}} } int main() {cin>>n>>m;int u,v;int num = 0;for(int i = 0; i < m; i++)//畫出連接表 {cin>>u>>v; link[u][v] = link[v][u] = 1;}cin>>u>>b;//輸入最后兩個數字dfs(u); for(int i = 1; i <= n; i++){if(count[i] == roads && i!=u && i!=b){num++;}}cout<<num<<endl; }

?

總結

以上是生活随笔為你收集整理的蓝桥杯_风险度量（一题多解）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。