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

解题思路:

注意事项:

参考代码:

#include<iostream>

#include<string>

#include<algorithm>

#include<string.h>

using namespace std;

int arr[1001];

int tag[1001];

int b[2001][2001];

int n,m;

int t,tt,sum;

int dfs(int k){

if(k == tt){

sum++;

return 1;

}

int flag = 0;

for(int i=1; i<=n; i++)

if(tag[i]==0 && b[k][i] == 1){

tag[i] = 1;

flag += dfs(i);

tag[i] = 0;

}

arr[k] += flag; 

return flag;

}

int main(){

cin>>n>>m;

for(int i=1; i<=m; i++){

cin>>t>>tt;

b[t][tt] = 1;

b[tt][t] = 1;

}

cin>>t>>tt;

tag[t] = 1;

if(!dfs(t))

cout<<-1<<endl;

else{

int j=0;

for(int i=1;i<=n;i++)

if(arr[i] == sum)

j++;

cout<<j-1<<endl;

}

return 0;

}