玉面小蛟龙


私信TA

用户名:2410056091

访问量:2966

签 名:

等  级
排  名 249
经  验 3535
参赛次数 30
文章发表 33
年  龄 0
在职情况 学生
学  校
专  业

  自我简介:

解题思路:

1433.PNG

从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;
}


 

0.0分

0 人评分

  评论区