#|【图论】B055_LQ_危险系数（利用 dfs 求割点的思想） #|图论

抗日战争时期，冀中平原的地道战曾发挥重要作用。
地道的多个站点间有通道连接，形成了庞大的网络。但也有隐患，当敌人发现了某个站点后，其它站点间可能因此会失去联系。
我们来定义一个危险系数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

方法一：利用 dfs 求割点的思想如果一个点 v 在 s–>e 的所有路径中都出现了一次，就证明这些路径都经过了 v 点，也就是说关键点 v 的存在是 s —> e 所有路径连通的充要条件；
如果 v 没在所有 s->e 的路径中的任意一条出现一次，那么敌人就有可能通过其它不经过 v 的路径到达 e

#include using namespace std; const int N=1005; int n, m, s, e, way, vis[N], cnt[N], path[N]; vector> g; void dfs(int u, int sz) { if (u==e) { way++; for (int i=0; i; i++) cnt[path[i]]++; return; } for (int v : g[u]) if (!vis[v]) { vis[v]=1, path[sz]=v; dfs(v, sz+1); vis[v]=0; } } int main() { std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>m; g.resize(n+1); for (int j=0; j>u>>v; g[u].emplace_back(v), g[v].emplace_back(u); } cin>>s>>e; path[0]=s, vis[s]=1; dfs(s,1); if (way==0) { cout << -1; } else { int ans=0; for (int i=1; i<=n; i++) if (cnt[i]==way) { ans++; } cout << ans-2; } return 0; }

【#|【图论】B055_LQ_危险系数（利用 dfs 求割点的思想）】复杂度分析