做过一样的 怎么又忘了 再一次搜超时
不用回溯
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 #include<queue> 8 using namespace std; 9 #define N 10010 10 int n,m; 11 vector<int>ed[N]; 12 bool vis[N][N]; 13 int pa[100010],t; 14 void dfs(int u) 15 { 16 int i; 17 for(i = 0 ; i < (int)ed[u].size() ; i++) 18 { 19 int v = ed[u][i]; 20 if(!vis[u][v]) 21 { 22 vis[u][v] = 1; 23 dfs(v); 24 } 25 } 26 t++; 27 pa[t] = u; 28 return ; 29 } 30 int main() 31 { 32 int i,j,u,v; 33 scanf("%d",&n); 34 for(i = 1; i <= n ; i++) 35 { 36 scanf("%d",&m); 37 scanf("%d",&u); 38 for(j = 1 ; j <= m ; j++) 39 { 40 scanf("%d",&v); 41 ed[u].push_back(v); 42 u = v; 43 } 44 } 45 dfs(1); 46 printf("%d ",t-1); 47 for(i = t; i > 1 ; i--) 48 printf("%d ",pa[i]); 49 printf("%d ",pa[1]); 50 return 0; 51 }