原题链接 思路： 如果有环，则起点一定为“1”。如果没有可以胜过“1”的，则无环。 根据W，L来建立图，用dfs从1节点遍历+回溯。 剪枝：dfs到某个子序列时，如果当前未访问节点无法与1节点构成回路，就不往下搜索。
import java.util.*; public class Main { static int[][] map = new int[21][21]; static int[] visit = new int[21]; static int flag = 0; static int[] res = new int[21]; static int n = 0; static void dfs(int x, int deep) { if (flag == 1) { return; } res[deep] = x + 1; if (deep == n - 1) { if (map[x][0] == 1) flag = 1; return; } int j = 1; for (j = 1; n > j; j++) { if (visit[j] == 0 && map[j][0] == 1) { break; } } if (j == n) { return; } for (int i = 1; i < n; i++) { if (visit[i] == 0 && map[x][i] == 1) { visit[i] = 1; dfs(i, deep + 1); visit[i] = 0; } } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); for (int i = 0; i < n; i++) { String s = sc.next(); for (int j = 0; j < n; j++) { if(s.charAt(j)=='W') map[i][j]=1; if(s.charAt(j)=='L') map[j][i]=1; } } visit[0] = 1; dfs(0, 0); if (flag == 1) { for (int i = 0; i < n - 1; i++) { System.out.print(res[i] + " "); } System.out.print(res[n - 1]); } else { System.out.print("No Solution"); } sc.close(); } }转载于:https://www.cnblogs.com/ruoh3kou/p/9971424.html
