蓝桥杯2013年第四届真题-危险系数 （C++代码）

解题思路:

注意事项:

参考代码:

#include<iostream>
#include<cstring>
using namespace std;
const int M=1000+5;
int map[M][M],visit[M],cunt[M];
int n,m,a,b;
int dfs(int t)
{
	if(t==b)
	{
		return 1;
	}
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		if(i!=t&&visit[i]==0&&map[t][i])
		{
			visit[i]=1;
			sum+=dfs(i);
			visit[i]=0;
		}
	}
	if(t!=a)
	cunt[t]+=sum;
	return sum;
}
int main()
{
	while(cin>>n>>m)
	{
		int x,y;
		memset(visit,0,sizeof(visit));
		while(m--)
		{
			cin>>x>>y;
			map[x][y]=map[y][x]=1;		
		}
		cin>>a>>b;
		visit[a]=1;
		int s=dfs(a);
		int ans=0;
		for(int i=1;i<=n;i++)
		{
			if(cunt[i]==s)
			ans++;
		}
		if(ans)
		cout<<ans<<endl;
		else
		cout<<-1<<endl;
	}
	return 0;
}