直接暴力，复杂度O((V+E)*V) ：（3000*1000=3*10^6，可以）
AC代码：
#include <stdio.h> #include <memory.h> #include <math.h> #include <string> #include <string.h> #include <vector> #include <set> #include <stack> #include <queue> #include <algorithm> #include <map> #define I scanf #define OL puts #define O printf #define F(a,b,c) for(a=b;a<c;a++) #define FF(a,b) for(a=0;a<b;a++) #define FG(a,b) for(a=b-1;a>=0;a--) #define LEN 3000 #define MAX 0x06FFFFFF #define V vector<int> using namespace std; int N,M,S,E; vector<int> g[LEN]; int vis[LEN]; void dfs(int s,int drop){ vis[s]=1; int i; FF(i,g[s].size()){ int to=g[s][i] ; if(!vis[to] && to!=drop){ dfs(to,drop); } } // vis[s]=0; } int main(){ // freopen("D:/CbWorkspace/blue_bridge/危险系数.txt","r",stdin); I("%d%d",&N,&M); int i,j,a,b; FF(i,M){ I("%d%d",&a,&b); g[a].push_back(b); g[b].push_back(a); } I("%d%d",&S,&E); dfs(S,-1); if(!vis[E]){ puts("-1"); return 0; } int ans=0; F(i,1,N+1){ memset(vis,0,sizeof vis); if(i!=S && i!=E){ dfs(S,i); if(!vis[E]) ans++; } } O("%d ",ans); return 0; }
使用割点，复杂度O(V+E)：
其实不用网上找的判割点的骚方法，直接记录每个点连通到终点的路径数，最后遍历所有点，如果这个数等于总路径，ans+=1 。记得最后输出的是ans-1的值
#include <stdio.h> #include <memory.h> #include <math.h> #include <string> #include <string.h> #include <vector> #include <set> #include <stack> #include <queue> #include <algorithm> #include <map> #define I scanf #define OL puts #define O printf #define F(a,b,c) for(a=b;a<c;a++) #define FF(a,b) for(a=0;a<b;a++) #define FG(a,b) for(a=b-1;a>=0;a--) #define LEN 3000 #define MAX 0x06FFFFFF #define V vector<int> using namespace std; int N,M,S,E; vector<int> g[LEN]; int vis[LEN]; int cnt[LEN]; vector<int> path; int pathNum=0; void dfs(int s){ int i; if(s==E) { //遍历到了终点 pathNum++; FF(i,path.size()){ cnt[path[i]]++; //记录通过这个点有几条路径到达终点 } return; } path.push_back(s); //入栈 vis[s]=1; FF(i,g[s].size()){ int to=g[s][i] ; if(!vis[to]){ dfs(to); } } vis[s]=0; path.pop_back(); //出栈 } int calc(){ int i,ans=0; F(i,1,N+1){ if(cnt[i]==pathNum) ans++; } return ans-1;//不包括源点 } int main(){ // freopen("D:/CbWorkspace/blue_bridge/危险系数.txt","r",stdin); I("%d%d",&N,&M); int i,j,a,b; FF(i,M){ I("%d%d",&a,&b); g[a].push_back(b); g[b].push_back(a); } I("%d%d",&S,&E); dfs(S); O("%d ",calc()); return 0; }
用时对比：
