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

解题思路:

从1-6：有两条路径：13456

1356

题目中关键点的意思：从1-6中必须经过的点，无论多少条路到6，都必须经过的点
深搜，找出所有路径，统计每条路径中经过的站点，计数加一

当某站点的计数等于所有路径时（每条路径都经过的站点）。13456,1356两条路径重复的点有1356，除去起点和终点，剩余：3 5

AC代码:

#include<stdio.h>
int n,m,u,v,cou=0,cou1=0;
int a[1002][1002],b[1002],c[1002];//a[][]存放站点间的通道（有为1，无为0），b[]在某条路径中经过的点（1经过，0没有），c[]所有路径里面每个点出点的次数 
void dfs(int i)	//找出所有n,v之间的路径 
{	int x,y;
	if(i==v)	//到达目标点，通过b[]将经过的点加1 
		{	cou++;
			for(y=1;y<=n;y++)	//该路径上的点计数加一 
				if(b[y]==1)
					c[y]++;	
			return ;
		}
	else {
		for(x=1;x<=n;x++)	//遍历所有点 
			{
				if(a[i][x]==1&&b[x]==0)	//和i点联通，并且未被走过 
					{
						b[x]=1;	//标记走了 
						dfs(x);	//回溯，取消标记 
						b[x]=0;
					}
			}
	}
}
int main()
{	int i;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
		{
			scanf("%d%d",&u,&v);
			a[u][v]=1;	//无向图 
			a[v][u]=1;
		}	
	scanf("%d%d",&u,&v);
	b[u]=1;
	dfs(u);
	if(cou==0)	//没有一条路径是通的 
		{
			printf("-1");
			return 0;	
		}
	else 
	{
		for(i=1;i<=n;i++)	//找出几条路劲，关键路径上的点与路径数相同 
			if(c[i]==cou)
				cou1++;
		printf("%d",cou1-2);	//除去起始点和终点 
	}
	return 0;
}