抗日战争时期，冀中平原的地道战曾发挥重要作用。
地道的多个站点间有通道连接，形成了庞大的网络。但也有隐患，当敌人发现了某个站点后，其它站点间可能因此会失去联系。
我们来定义一个危险系数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 6 1 3 2 3 3 4 3 5 4 5 5 6 1 6 样例输出 2 #include<iostream> #include<vector> using namespace std; const int maxd=1010; struct Point{ vector<int> v;//点p[x]的相邻点； int status;//访问状态 }p[maxd]; int x1,x2,flag=0; void f(int x){ p[x].status=1; if(x==x2){ flag=1;//如果flag为1代表这不是关键点 return; } for(vector<int>::iterator it=p[x].v.begin();it!=p[x].v.end();it++){ if(!p[*it].status){ f(*it); } } } int main(){ int n,m,i,ctn=0; cin>>n>>m; for(i=1;i<=n;i++){ p[i].status=0; } for(i=0;i<m;i++){ cin>>x1>>x2; p[x1].v.push_back(x2); p[x2].v.push_back(x1); } cin>>x1>>x2; for(i=1;i<=n;i++){ if(i!=x1&&i!=x2){ p[i].status=1;//设为关键点 f(x1);//从x1出发看是否能到s2（测试是否为关键点） if(flag==0)ctn++; flag=0; for(int j=1;j<=n;j++){ p[j].status=0; } } } cout<<ctn; return 0; }