这个题主要是做好如何处理割点问题，就是记录每一次找到一个路径，就把每一个的该路径上的点多一次计数，同时我们要找到所有路径的个数，全部找到完以后遍历count数组，如果找到和我们路径数相同的，就让最终输出值+1 ；
#include<iostream> #include<cstring> #include<algorithm> #include<vector> using namespace std ; const int N = 1010 ; int n , m ; int x,y; int path[N] ;//记录路径，因为我们要找到最后的路径要判断是否走到终点 vector<int> a[N] ; int v[N] ; int c[N] ; int cnt ; int ans ; void dfs1(int u , int fa){ if(path[u-1] == y){//走到终点 for(int i = 1 ; i <= n ; i ++) if(v[i]) c[i] += 1 ;//走到终点就记录每一个走过的点计数+1 cnt ++ ; return ; } for(int i = 0 ; i < a[fa].size() ; i ++){//排列 if(!v[a[fa][i]]){ v[a[fa][i]] = 1 ; path[u] = a[fa][i] ; dfs1(u + 1 ,a[fa][i]) ; path[u] = a[fa][i] ; v[a[fa][i]] = 0 ; } } } int main(){ cin >> n >> m ; while(m -- ){ int i, j ; cin >> i >> j ; a[i].push_back(j) ; a[j].push_back(i) ; } cin >> x >> y ; //for(int i = 1 ; i <= 6 ; i ++) cout << a[i][1] << " " ;cout<< endl ; path[0] = x ; v[x] = 1 ; dfs1(1,x) ; //cout << cnt << endl ; //for(int i = 0 ; i < cnt ; i ++) cout << path[i] << " " ; for(int i = 1 ; i <= n ; i ++ ) if(c[i] == cnt) ans ++ ; cout << ans - 2<< endl ; return 0 ; }
