|
最近在練Tarjan,看到這道題目分類(lèi)在割點(diǎn)里面就想嘗試做一下，點(diǎn)開(kāi)發(fā)現(xiàn)題目數(shù)據(jù)范圍竟然如此之小，算了，bfs暴力一發(fā)。 題目意思就是你需要找到一個(gè)關(guān)鍵節(jié)點(diǎn)，也可以理解成，行軍打仗時(shí)必需經(jīng)過(guò)的地方，敵軍想從a點(diǎn)到b點(diǎn)必需經(jīng)過(guò)的節(jié)點(diǎn)，在這個(gè)地方你一定能阻擊到敵軍，我感覺(jué)我比喻的應(yīng)該還算形象。 既然如此，要找最小的這種節(jié)點(diǎn)，我們可以把節(jié)點(diǎn)1到n開(kāi)始枚舉，如果不經(jīng)過(guò)這個(gè)節(jié)點(diǎn)所相連的邊還能到達(dá)終點(diǎn)，那么這個(gè)節(jié)點(diǎn)就是不合理的，反之，能到達(dá)終點(diǎn)，這個(gè)節(jié)點(diǎ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){ //不能經(jīng)過(guò)限制節(jié)點(diǎn)
//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;
}
|
|
|
來(lái)自： 新進(jìn)小設(shè)計(jì) > 《待分類(lèi)》
