蓝桥杯2013年第四届真题-危险系数 （C++代码）dfs

解题思路:

注意事项:

参考代码:

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int maxn = 100005;
int vis[maxn];
int cns[maxn];
int n, m, u, v;
int ans = 0;
int sum = 0;
vector<int> p[maxn];
void dfs(int x)
{
    if(x == v)
    {
        for(int i = 1; i <= n; i++)
        {
            if(vis[i] != 0 && i != u && i != v) cns[i]++;
        }
        ans++;
        return ;
    }
    else
    {
        for(int i = 0; i < p[x].size(); i++)
        {
            if(vis[p[x][i]] == 0)
            {
                vis[p[x][i]] = 1; 
                dfs(p[x][i]);
                vis[p[x][i]] = 0;
            }
        } 
    }
    return;
}
int main()
{
    memset(vis,0,sizeof(vis));
    int a, b;
    cin>>n>>m;
    for(int i = 0; i < m; i++)
    {
        cin>>a>>b;
        p[a].push_back(b);    
        p[b].push_back(a);
    }
    cin>> u>> v;
    vis[u] = 1;
    dfs(u);
    for(int i = 1; i <= n; i++)
    {
        if(cns[i] == ans)
        {
            sum++;
        }
    }
    cout<<sum;
    return 0;
}