判断无向图两点间是否存在长度为K的路径
程序员文章站
2022-03-09 23:41:09
1 #include 2 #include 3 #define MAXN 5 4 using namespace std; 5 6 struct edge 7 { 8 int f,t; 9 edge(int f, int t) :f(f), t(t) {} 10 }; 11 12 vector ed... ......
1 #include <iostream> 2 #include <vector> 3 #define MAXN 5 4 using namespace std; 5 6 struct edge 7 { 8 int f,t; 9 edge(int f, int t) :f(f), t(t) {} 10 }; 11 12 vector<edge> edges; 13 vector<int> G[MAXN+1]; 14 bool vis[MAXN+1]; 15 16 void init(){ 17 for (int i = 1; i <= MAXN; i++) 18 vis[i] = false; 19 } 20 21 22 //通过缩短路径方法求解 23 bool search_k_path(int begin,int end,int k){ 24 if(begin==end && k==0) return true; 25 //当要求的K大于 i 到 j 的长度,当 I ==J 时,k<0 26 if(k>0){ 27 vis[begin] = true; 28 for(int i=0;i<G[begin].size();i++){ 29 if(!vis[edges[G[begin][i]].t]) 30 return search_k_path(edges[G[begin][i]].t,end,k-1); 31 } 32 vis[begin] = false; 33 } 34 return false; 35 } 36 37 38 39 int main(int argc, char const *argv[]) 40 { 41 //input data 42 43 int s,e; 44 for(int i= 0 ;i<7;i++){ 45 cin>>s>>e; 46 edges.push_back(edge(s,e)); 47 G[s].push_back(edges.size()-1); 48 edges.push_back(edge(e,s)); 49 G[e].push_back(edges.size()-1); 50 } 51 init(); 52 cout <<search_k_path(1,5,2)<<endl; 53 54 return 0; 55 }
上一篇: 只有一个人没变