问题描述抗日战争时期，冀中平原的地道战曾发挥重要作用。地道的多个站点间有通道连接，形成了庞大的网络。但也有隐患，当敌人发现了某个站点后，其它站点间可能因此会失去联系。我们来定义一个危险系数DF(x,y)：对于两个站点x和y (x != y), 如果能找到一个站点z，当z被敌人破坏后，x和y不连通，那么我们称z为关于x,y的关键点。相应的，对于任意一对站点x和y，危险系数DF(x,y)就表示为这两点之间的关键点个数。本题的任务是：已知网络结构，求两站点之间的危险系数。输入格式输入数据第一行包含2个整数n(2 <= n <= 1000), m(0 <= m <= 2000),分别代表站点数，通道数；接下来m行，每行两个整数 u,v (1 <= u, v <= n; u != v)代表一条通道；最后1行，两个数u,v，代表询问两点之间的危险系数DF(u, v)。输出格式一个整数，如果询问的两点不连通则输出-1.样例输入7 61 32 33 43 54 55 61 6样例输出2
代码如下：
1 #include2 #include 3 #include 4 #define Max_ 3000 5 6 typedef struct node node_t; 7 typedef struct node 8 { 9 int n; //下一个站点 10 node_t *next;11 }node;12 13 int n,m,u,v,res;14 int vis[Max_]; //标记站点是否被访问 15 int walk[Max_]; //记录单次行走路径的站点 16 int use[Max_]; //标记成功路径下的站点次数 17 node *e[Max_]; //邻接表，记录各站点之间的联系 18 19 20 void add_edge(int x,int y)//添加两站点之间的边21 {22 node *p;23 p = (node*)malloc(sizeof(node));24 p->n = y;25 p->next = e[x];26 e[x] = p;27 return ;28 }29 30 void init()//初始化 31 { 32 int i,x,y;33 34 memset(vis,0,sizeof(vis));35 memset(walk,0,sizeof(walk));36 memset(use,0,sizeof(use));37 for (i=0 ; i<=n ; i++)38 e[i] = NULL;39 40 scanf("%d%d",&n,&m); //站点，通道数41 42 for (i=0 ; i n] == 0)//下一个站点未被访问 69 {70 vis[p->n] = 1;71 DF(p->n,step+1);72 vis[p->n] = 0;73 }74 p = p->next;//查找当前与站点连接的下一个站点 75 } 76 77 return ;78 }79 80 int main(void)81 {82 int i,k;83 init();84 k = res = 0;85 86 vis[u] = 1; //标记起点访问 87 DF(u,0);88 89 for (i=0 ; i<=n ; i++)90 if (use[i]==res)//站点标记数，与成功路径数相同，即为u与v的关键点 91 k ++;92 93 printf("%d",k-1);94 return 0;95 }
错误：理解为寻找最短路径，实际是寻找能被多次抵达终点的站点数（与成功抵达终点的次数相同）
解题思路：
建立站点之间联系，遍历能够抵达终点的路径，并对成功路径上的站点做次数+1
当遍历完成后，查找与成功次数相同的站点（即该站点与抵达终点有必然关系）