危险系数（关键点+路径）

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <string>
 5 #include <math.h>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <stack>
 9 #include <queue>
10 #include <set>
11 #include <map>
12 #include <sstream>
13 const int INF=0x3f3f3f3f;
14 typedef long long LL;
15 const double eps =1e-8;
16 const int mod=1e9+7;
17 const int maxn=1e6+10;
18 using namespace std;
19 
20 vector<int> vt[1005];
21 int num[1005];//记录路径中每个点经过次数 
22 int vis[1005];//记录路径 
23 int cnt;//路径数 
24 int n,m,st,ed;
25 
26 void DFS(int u)
27 {
28     if(u==ed)//到达终点
29     {
30         cnt++;
31         for(int i=1;i<=n;i++)
32         {
33             if(vis[i]) num[i]++; 
34         }
35         return;
36     }
37     for(int i=0;i<vt[u].size();i++)
38     {
39         int v=vt[u][i];
40         if(vis[v]==0)
41         {
42             vis[v]=1;
43             DFS(v);
44             vis[v]=0;
45         }
46     }
47     return ;
48 }
49 
50 int main()
51 {
52     #ifdef DEBUG
53     freopen("sample.txt","r",stdin);
54     #endif
55     
56     scanf("%d %d",&n,&m);
57     for(int i=1;i<=m;i++)
58     {
59         int u,v;
60         scanf("%d %d",&u,&v);
61         vt[u].push_back(v);
62         vt[v].push_back(u);
63     }
64     scanf("%d %d",&st,&ed);
65     vis[st]=1;
66     DFS(st); 
67     int ans=0;
68     for(int i=1;i<=n;i++)
69     {
70         if(num[i]==cnt) ans++;
71     }
72     if(cnt>0) printf("%d\n",ans-2);//起点和终点不算割点,减去 
73     else printf("-1\n");
74     
75     return 0;
76 }