bfs+dfs(判断是否是关键点)

解题思路:
        1.用bfs求出图的start 和  target  最短路径，因为要求关键点就是求start 到 target 路径上的关键点

        2.用dfs判断路径上的点是否为关键点
注意事项:

参考代码:

#include <bits/stdc++.h>
using namespace std;
typedef struct node{
	int v;
	int step;
}node;
int vis[3000]={0};
int maze[3000][3000]={0};
int n,m,targetS,targetE;//n是点的个数 m是边的个数 
vector<int> vs(3000,0);
int flg=1;
void dfs(int sv,int ev ){ //查看是否为关键点 
	if(sv==targetE){ //不是关键点 
		flg=0;
		return;	
	}
	for(int i=1;i<=n;i++){
		if(i!=ev && maze[sv][i]==1 && vs[i]==0){
			vs[sv]=1;
			dfs(i,ev);
//			vis[sv]=0;
		}
	}
}
int main(){
	//用bfs找到一个最短的路径，这个路径就是关键路径，然后判断每个点是否为关键点 
	cin>>n>>m;
	
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		maze[a][b]=1;
		maze[b][a]=1;
	}
	cin>>targetS>>targetE;
	if(targetS==targetE){
		cout<<0;
		return 0;
	} 
	queue<node>q;
	node t;
	t.v=targetS;
	vis[t.v]=1;
	t.step=0; 
	q.push(t);
	while(!q.empty()){
		node t=q.front();
		if(t.v==targetE){
			cout<<t.step-1;
			return 0;
		}
		q.pop();
		for(int i=1;i<=n;i++){
			if(vis[i]==0 && maze[t.v][i]==1){
				node tmp;
				tmp.v=i;
				vs[targetS]=1;
				dfs(targetS,i);//判断这个点是否是关键点 
				std::fill(vs.begin(),vs.end(),0);
				if(flg)
					tmp.step=t.step+1;
				else{
					tmp.step=t.step;
					flg=1;
				}
				vis[i]=1;
				q.push(tmp);
			}
		}
	}
	cout<<-1;
	return 0;
}