華為機試0406 第二題（DFS）

DFS版本

思路：

• DFS 判斷是否有環，隻要一條路徑有環就不行，直接傳回輸出-1；
• 在 DFS 過程中使用 TreeSet 記錄所有依賴點即可，如果不存在環，就是所有的依賴點了。

package huawei.oj_0406;

import java.util.*;

public class Solution2 {
    private static boolean haveLoop = false;
    private static Set<Integer> dependments;
    private static int m;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        m = Integer.parseInt(sc.nextLine());
        List<Integer>[] parents = new List[n];
        for(int i = 0; i < n; i++){
            parents[i] = new ArrayList<>();
            String[] strs = sc.nextLine().split(",");
            int k = Integer.parseInt(strs[0]);
            for(int j = 1; j <= k; j++)
                parents[i].add(Integer.parseInt(strs[j]));
        }

        dependments = new TreeSet<>();
        dfs(parents, m, new boolean[n]);
        if(haveLoop)
            System.out.println(-1);
        else{
            Integer[] res = dependments.toArray(new Integer[0]);
            System.out.print(res[0]);
            for(int i = 1; i < res.length; i++)
                System.out.print("," + res[i]);
        }
    }

    private static void dfs(List<Integer>[] parents, int i, boolean[] visited){
        if(visited[i] == true){
            haveLoop = true;
            return;
        }
        if(!haveLoop){
            if(m != i)
                dependments.add(i);
            visited[i] = true;
            for(int j : parents[i])
                dfs(parents, j, visited);
            visited[i] = false;
        }
    }
}