思路: 关键在于怎么记录返回的路径.比如题目给出的第一个样例 这里从1出发,我们的dfs函数最终会搜到6,这时候我们其他点都被标记为已访问,所以dfs函数就会一层一层的返回,先是返回到点5,然后是点4,所以我们可以直接记录下返回路径. dfs(i)下面就是代表返回的位置,在这里记录返回的点也就是s. 每一层的s都不同,当达到6的时候s就代表5.
然后就是不联通的情况:
这里从6出发,到搜到最后会是在5这个点,然后一层一层返回.所以path数组记录的是6 4 5 4 6,然后我们最后判断下是否所有点被标记过,若不是最后输出一个0 .
代码:
import java.io.*; import java.util.StringTokenizer; public class S7_15 { static int n, m, start; static int G[][] = new int[1005][1005]; // 存放边 static int vis[] = new int[1005]; // 看该节点是否被访问 static int path[] = new int[2005]; // 存放路径 有可能重复所以开2005 static int pathIndex; // 记录路径的下标 static boolean ok = true; // 判断该图是否连通图 public static void main(String[] args) throws IOException { S15.init(System.in); n = S15.nextInt(); m = S15.nextInt(); start = S15.nextInt(); for (int i = 0; i < m; i++) { int a = S15.nextInt(); int b = S15.nextInt(); G[a][b] = G[b][a] = 1; } vis[start] = 1; // 标记起点为已经访问 path[pathIndex++] = start; // 记录起点路径 dfs(start); // 打印结果 for (int i = 1; i <= n; i++) { if (vis[i] == 0) { // 表明节点未访问过 ok = false; // 代表不是联通图 break; } } if (ok) { System.out.print(path[0]); for (int i = 1; path[i] != 0; i++) { System.out.print(" " + path[i]); // 这里先打印空格就不会出现最后保留空格的情况了 } } else { for (int i = 0; path[i] != 0; i++) { System.out.print(path[i] + " "); } System.out.print("0"); } } static void dfs(int s) { for (int i = 1; i <= n; i++) { if (G[s][i] == 1 && vis[i] == 0) { // 有边且未访问过 vis[i] = 1; // 标记为已访问 path[pathIndex++] = i; dfs(i); // 上面完成 后到这一步代表是从后面返回 所以记录返回路径 path[pathIndex++] = s; // 每一函数 返回路径都是s("起点") // 不用回溯 vis了 因为要么找到路 要么没有找到. 找到路也要返回 没有找到也要返回. 如果回溯有可以访问这个节点了 } } } } class S15 { static BufferedReader reader; static StringTokenizer tokenizer; static void init(InputStream input) { reader = new BufferedReader(new InputStreamReader(input)); tokenizer = new StringTokenizer(""); } static String next() throws IOException { while (!tokenizer.hasMoreTokens()) { tokenizer = new StringTokenizer(reader.readLine()); } return tokenizer.nextToken(); } static int nextInt() throws IOException { return Integer.parseInt(next()); } } #include<iostream> #include<string.h> using namespace std; int arr[1005][1005]; int vis[1005]; int n,m,s; int count; bool flag=false; void dfs(int now){ if(count==n){ cout<<now<<' '; flag=true; return; } cout<<now<<' '; for(int i=1;i<=n;i++){ if(arr[now][i]==1&&vis[i]==0){ count++; vis[i]=1; dfs(i); if(now==s){ cout<<now; } else cout<<now<<' '; } } return; } int main(){ int x,y; memset(arr,0,sizeof(arr)); memset(vis,0,sizeof(vis)); cin>>n>>m>>s; for(int i=0;i<m;i++){ cin>>x>>y; arr[x][y]=1; arr[y][x]=1; } vis[s]=1; count=1; dfs(s); if(!flag) cout<<' '<<0; return 0; }