TZOJ6556: 嗅探器

chendongyu 2021-02-04 原文

最近在练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;
}