题解 | 星途勘测

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    // public static List<List<Integer>> list = new ArrayList<>();
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int s = in.nextInt();
        int t = in.nextInt();
        int[][] arr = new int[m][3];
        for (int i = 0; i < m; i++) {
            arr[i][2] = i + 1; //索引
            arr[i][0] = in.nextInt(); // start
            arr[i][1] = in.nextInt(); //end
        }
        int q = in.nextInt();
        boolean[] used = new boolean[m];
        Arrays.fill(used, false);
        List<List<Integer>> list = new ArrayList<>();
        boolean[] usedN = new boolean[n];
        Arrays.fill(usedN, false);
        usedN[s - 1] = true;
        dfs(new ArrayList<Integer>(), arr, s, t, usedN,used, list);
        Collections.sort (list, (a, b) -> {
            int minLen = Math.min (a.size (), b.size ());
            for (int i = 0; i < minLen; i++) {
                int cmp = a.get (i).compareTo (b.get (i));
                if (cmp != 0) return cmp;
            }
            return Integer.compare (a.size (), b.size ());
        });

        for (int i = 0; i < q; i++) {
            int des = in.nextInt();
            int num = 0;
            List<Integer> ans = new ArrayList<Integer>();
            for (int j = 0; j < list.size(); j++) {
                if (list.get(j).contains(Integer.valueOf(des))) {
                    num++;
                    ans.add(j + 1);
                }
            }
            System.out.print(num + " ");
            for (int j = 0; j < ans.size(); j++) {
                System.out.print(ans.get(j) + " ");
            }
            System.out.println();
        }


    }
    public static void dfs(List<Integer> res, int[][] arr, int start, int end,
                           boolean[] usedN, boolean[] used, List<List<Integer>> list) {
        if (start == end) {
            // Collections.sort(res);
            list.add(new ArrayList<Integer>(res));
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            if (used[i] == false) {
                if (arr[i][0] == start && usedN[arr[i][1]-1]==false) {
                    res.add(arr[i][2]);
                    used[i] = true;
                    usedN[arr[i][1]-1]=true;
                    dfs(res, arr, arr[i][1], end, usedN,used, list);
                    used[i] = false;
                    res.remove(res.size() - 1);
                    usedN[arr[i][1]-1]=false;
                }
                if (arr[i][1] == start && usedN[arr[i][0]-1]==false) {
                    res.add(arr[i][2]);
                    used[i] = true;
                    usedN[arr[i][0]-1]=true;
                    dfs(res, arr, arr[i][0], end, usedN,used, list);
                    used[i] = false;
                    res.remove(res.size() - 1);
                    usedN[arr[i][0]-1]=false;
                }
            }
        }
    }
}