1433: 蓝桥杯2013年第四届真题-危险系数（无向图+dfs）

解题思路: 将地道的站点化作无向图，然后依次假设各个站点被炸毁，如果被炸毁后无法到达目标站点则被炸毁的站点就是关键站点，那么危险系数就+1.

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;
int n,m;
int ma[1005][1005];
int u,v;
int f[1005];//表示该站点是否已经走过
int ff[1005];//表示该站点是否炸毁
int flag=0;
void dfs(int u,int v)
{
	f[u]=1;//表示该站点走过了
	if(u==v)//到达终点站点
	{
		flag=1;//标记到达了终点
		return;
	}
	for(int i=1;i<=n;i++)
	{
		if(ma[u][i]==1&&f[i]!=1&&ff[i]==0)
		{
			dfs(i,v);
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++)//建立无向图
	{
		int a,b;
		scanf("%d%d",&a,&b);
		ma[a][b]=1;
		ma[b][a]=1;
	}
	int ans=0;//危险系数
	scanf("%d%d",&u,&v);
	dfs(u,v);//先试验所给的两个站点是否相通
	if(flag==0)//不通就输出-1
	{
		printf("-1");
		return 0;
	}
	flag=0;
	memset(f,0,sizeof(f));
	for(int i=1;i<=n;i++)
	{
		if(i==u||i==v)//不能假设起点站和终点站被炸毁
		{
			continue;
		}
		ff[i]=1;//当前站点被炸毁
		dfs(u,v);
		ff[i]=0;//恢复当前站点
		if(flag==0)//无法联通说明是关键站点
		{   
			ans++;	
		}
		flag=0;
		memset(f,0,sizeof(f));
	}
	printf("%d",ans);
	return 0;
}