[蓝桥杯][2013年第四届真题]危险系数(DFS)

地址：https://www.dotcpp.com/oj/problem1433.html

中文题意

解析：

从u->v，如果中间经过的点的被访问次数等于u->v的路线数，便是一个关键点。

具体见注释。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e3+50;
int vis[maxn],su[maxn];
const int inf=1e9;
vector<int>v[maxn];
int a,b;
int n,m;
int cnt=0;
void dfs(int u)
{
    if(u==b)
    {
        cnt++;    //路线数
        for(int i=1;i<=n;i++)
        {
            su[i]+=vis[i];    //记录i点的被访问次数        
        }
        return ;
    }
    vis[u]=1;//标记被访问
    for(int i=0;i<v[u].size();i++)
    {
        if(vis[v[u][i]]==0)
        {
            dfs(v[u][i]);
        }
    }
    vis[u]=0;   
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    cin>>a>>b;
    dfs(a);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(i!=a&&i!=b&&su[i]==cnt)
            ans++;
    }
    if(!ans)
        cout<<"-1"<<endl;
    else
        cout<<ans<<endl;
}