[蓝桥杯][历届试题][dfs][割点]危险系数

开数组要注意位置!!!因为评测环境的不同可能会出错!!!

在函数中定义的变量,在栈上创建,全局定义的变量,在数据段上创建。
由于你的数组太大,会造成栈溢出,使得程序错误。堆栈据说是2M大小,而数据段要大很多,具体多大好像与系统环境相关。

记录S=>T路径数ans

给所以经过的点计数,存储在cnt[]中

cnt[X]==ans && X!=S && X!=T 则X为S=>T的一个割点

 1 #include <vector>
 2 #include <iostream>
 3 using namespace std;
 4 int ans,res;
 5 void dfs(vector<int>e[],vector<int>path,int u,int t,int vis[],int cnt[]){
 6     if(vis[u])return;
 7     if(u==t){
 8         ans++;
 9         path.push_back(t);        
10         for(int i=0;i<path.size();i++)cnt[path[i]]++;
11         path.pop_back();        
12     }
13     vis[u]=1;
14     path.push_back(u);
15     for(int i=0;i<e[u].size();i++)dfs(e,path,e[u][i],t,vis,cnt);    
16     path.pop_back();
17     vis[u]=0;
18 }
19 
20 const int N=1005;
21 int n,m;
22 int s,t;
23 vector<int>e[N],path;
24 int vis[N]={0},cnt[N]={0};
25 int main(){
26     //数组开在全局变量即可
27     cin>>n>>m;    
28     for(int i=0,a,b;i<m;i++)cin>>a>>b,e[a].push_back(b),e[b].push_back(a);
29     cin>>s>>t;    
30     dfs(e,path,s,t,vis,cnt);    
31     for(int i=1;i<=n;i++)if(cnt[i]==ans&&!(i==s||i==t))res++;
32     cout<<res<<endl;
33     return 0;
34 }
~~Jason_liu O(∩_∩)O
原文地址:https://www.cnblogs.com/JasonCow/p/14434690.html