最近在练Tarjan,看到这道题目分类在割点里面就想尝试做一下,点开发现题目数据范围竟然如此之小,算了,bfs暴力一发。
#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;
}