最近在練Tarjan,看到這道題目分類在割點里面就想嘗試做一下，點開發現題目資料范圍竟然如此之小，算了，bfs暴力一發，
題目意思就是你需要找到一個關鍵節點，也可以理解成，行軍打仗時必需經過的地方，敵軍想從a點到b點必需經過的節點，在這個地方你一定能阻擊到敵軍，我感覺我比喻的應該還算形象，
既然如此，要找最小的這種節點，我們可以把節點1到n開始列舉，如果不經過這個節點所相連的邊還能到達終點，那么這個節點就是不合理的，反之，能到達終點，這個節點就是合理的，
#include<bits/stdc++.h>
using namespace std;
int visit[1000];
vector<int> vec[1000];
int n;
void bfs(int s,int limit){
memset(visit,0,sizeof(visit));
queue<int> q;
q.push(s);
visit[s]=1;
while(!q.empty()){
int from=q.front();
q.pop();
for(int i=0;i<vec[from].size();++i){
int to=vec[from][i];
if(!visit[to]&&to!=limit){ //不能經過限制節點
//cout<<to<<endl;
visit[to]=1;
q.push(to);
}
}
}
}
int main(){
scanf("%d",&n);
int x,y;
while(~scanf("%d%d",&x,&y)&&x+y!=0){
vec[x].push_back(y);
vec[y].push_back(x);
}
int a,b;
scanf("%d%d",&a,&b);
for(int i=1;i<=n;++i){
if(i==a||i==b) continue;
bfs(a,i);
if(!visit[b]){
cout<<i<<endl;return 0;
}
}
cout<<"No solution"<<endl;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/256630.html
標籤：其他
上一篇：高級搜索演算法之迭代加深
下一篇：單向鏈表及使用Java代碼實作