菜单 学习猿地 - LMONKEY

VIP

开通学习猿地VIP

尊享10项VIP特权 持续新增

知识通关挑战

打卡带练!告别无效练习

接私单赚外块

VIP优先接,累计金额超百万

学习猿地私房课免费学

大厂实战课仅对VIP开放

你的一对一导师

每月可免费咨询大牛30次

领取更多软件工程师实用特权

入驻
46
0

TZOJ6556: 嗅探器

原创
05/13 14:22
阅读数 48091

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

  

相关热门文章

发表评论

0/200
46 点赞
0 评论
收藏