原题链接：蓝桥杯2013年第四届真题-危险系数
解题思路:我是菜鸡，我的想法是，关键点的含义就是从a到b的必经点。既然如此，设置一个数组x，设i为必经点，a到b有几条路径，x[i]就等于几。这样，每次深度优先搜索可以把途径的点先压入栈中，如果能达到b，则栈中所有点i让x[i]++，最后x数组中的最大值有多少个，也就有多少个必经点。
注意事项:提前把a和b压入栈中，设置visited数组防止图中的环导致的死循环。
参考代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | #include<iostream>#include<stack>using namespace std;int M,N; int edge[1000][1000]={0};int x[1000]={0};stack<int> q;stack<int> p;//用于将q内的元素取出并让x[i]++void f(int a,int b,bool* v){ for(int i=1;i<=M;i++) { if(edge[a][i]==1&&!v[i]) { if(i==b)//说明能够到达b点，则将这条路径经过的点取出，让x[i]++ { p=q; while(!p.empty()) { x[p.top()]++; p.pop(); } } else { q.push(i); v[i]=true; f(i,b,v); q.pop();// f之后相当于a,i这个路径搜索完了，让i出栈 v[i]=false;// a,i搜索完了以后，别人也要用i，所以v[i]=false } } }}int main(){ cin>>M>>N; int a,b; for(int i=0;i<N;i++) { cin>>a>>b; edge[a][b]=1; edge[b][a]=1; } cin>>a>>b; bool* visited=new bool[M];//是否访问过 for(int i=1;i<=M;i++) { visited[i]=false; } visited[a]=true; q.push(a); q.push(b); f(a,b,visited); int max=0; for(int i=1;i<=M;i++) { if(max<x[i]) max=x[i]; } if(max==0) cout<<-1;//如果没有路径 else { int count=-2;//输出的必经点不包括a和b for(int i=1;i<=M;i++) if(x[i]==max) count++; cout<<count; } return 0; }//我是菜鸡，所以写的有点乱，不喜勿喷呜呜呜 |
9.9 分
1 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复