代码随想录Day64

98.所有可达路径

题目：98. 所有可达路径 (kamacoder.com)

思路：果断放弃

答案

import java.util.*;

public class Main {
    private static List<List<Integer>> adjList;
    private static List<List<Integer>> allPaths;
    private static int target;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        
        adjList = new ArrayList<>();
        for (int i = 0; i < n + 1; i++) {
            adjList.add(new ArrayList<>());
        }
        
        for (int i = 0; i < m; i++) {
            int s = scanner.nextInt();
            int t = scanner.nextInt();
            adjList.get(s).add(t);
        }
        
        target = n;
        allPaths = new ArrayList<>();
        List<Integer> currentPath = new ArrayList<>();
        currentPath.add(1);
        
        findAllPaths(1, currentPath);
        
        if (allPaths.isEmpty()) {
            System.out.println("-1");
        } else {
            for (List<Integer> path : allPaths) {
                System.out.println(formatPath(path));
            }
        }
        
        scanner.close();
    }
    
    private static void findAllPaths(int currentNode, List<Integer> currentPath) {
        if (currentNode == target) {
            allPaths.add(new ArrayList<>(currentPath));
            return;
        }
        
        for (int nextNode : adjList.get(currentNode)) {
            currentPath.add(nextNode);
            findAllPaths(nextNode, currentPath);
            currentPath.remove(currentPath.size() - 1);
        }
    }
    
    private static String formatPath(List<Integer> path) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < path.size(); i++) {
            sb.append(path.get(i));
            if (i < path.size() - 1) {
                sb.append(" ");
            }
        }
        return sb.toString();
    }
}

小结

• 注意，要按照题目格式输出
• 使用回溯算法
  • 确认递归函数，参数
  • 确定终止条件
  • 处理目前搜索节点出发的路径